Escape Problem

Problem Statement: Given an \(n \times n\) grid and \(m\) starting points \((x_1,y_1), (x_2,y_2), \dots, (x_m,y_m)\), determine whether it is possible to find a simple path from each starting point to any cell on the boundary (i.e. a cell in the first row, last row, first column, or last column) such that the paths are vertex-disjoint (i.e. no two paths share any cell).

Explanation: All cells in the grid are white except for the \(m\) starting points (marked in black). A valid path is one that moves between adjacent cells (up, down, left, right) and does not go out of the grid. Even if a starting point is already on the boundary, its trivial path (consisting of the cell itself) counts as a valid escape. The challenge is to decide if there exist \(m\) vertex-disjoint paths connecting the starting points to the boundary.

Note: Any formulas in the statement are rendered in \(\LaTeX\) format.

inputFormat

The first line contains two integers (n) and (m) (grid size and number of starting points). Each of the following (m) lines contains two integers (x) and (y), the 1-indexed coordinates of a starting point. It is guaranteed that all starting points are distinct and (1 \le x,y \le n).

outputFormat

Output a single line containing either “YES” if there exists a set of (m) vertex-disjoint paths from the given starting points to the boundary of the grid, or “NO” otherwise.

sample

3 1
2 2

YES