题目描述

译自 CLRS Problem 26-1 Escape problem

在一个 $n\times n$ 的网格中有 $m$ 个起始点 $(x_1, y_1),$ $(x_2, y_2),$ $\dots,$ $(x_m, y_m)$，试问：能否为这些结点分别找一条到边界的路径，且这 $m$ 条路径互不相交（即任意两条路径上没有一个相同的结点）。

黑点表示起始点，其他点用白点表示。找出的路径用加粗的线表示。图 (a) 存在符合条件的 $m$ 条路径，图 (b) 则不存在。

输入格式

第一行是一个整数，为 $n$ $(1\le n≤35)$。

第二行还是一个整数，为 $m(1\le m\le n^2)$。

以下 $m$ 行，第 $(i+2)$ 行包含两个整数 $x_i$ 和 $y_i$，表示第 $i$ 行第 $j$ 列的点是起始点。保证起始点坐标互不相同。

输出格式

只包括一行。若存在逃脱输出 YES，不存在逃脱输出 NO。

6
10
2 2
2 4
2 6
3 1
3 2
3 4
3 6
4 2
4 4
4 6

YES