逃离
题目描述
**译自 CLRS Problem 26-1 Escape problem**
在一个 $n\times n$ 的网格中有 $m$ 个起始点 $(x_1, y_1),$ $(x_2, y_2),$ $\dots,$ $(x_m, y_m)$,试问:能否为这些结点分别找一条到边界的路径,且这 $m$ 条路径互不相交(即任意两条路径上没有一个相同的结点)。
![https://i.loli.net/2018/10/14/5bc2ec2948f8b.png](https://i.loli.net/2018/10/14/5bc2ec2948f8b.png)
黑点表示起始点,其他点用白点表示。找出的路径用加粗的线表示。图 (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`。
输入输出样例
输入样例 #1
6
10
2 2
2 4
2 6
3 1
3 2
3 4
3 6
4 2
4 4
4 6
输出样例 #1
YES