有一个大小为 $$$n \times n$$$ 的棋盘。 $$$m$$$ 车以这样的方式放置在其上:
- 没有两个车占据同一个单元格;
- 没有两只车会互相攻击。
车攻击其行或列中的所有单元格。
是否可以将一只车(您可以选择移动哪一只)移动到不同的单元格中,这样就不会出现两只车互相攻击的情况?如果没有其他车站在其路径上,则车可以移动到其行或列中的任何单元格。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2000$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 8$$$) - 棋盘的大小和车的数量。
接下来的 $$$m$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$) - 第 $$$i$$$ 车的位置:$$$x_i$$$ 是行,$$$y_i$$$是列。
没有两个车占据同一个牢房。没有两只车会互相攻击。
输出
对于每个测试用例,如果可以将一个车移动到不同的单元格中,则打印“YES”,以便没有两个车仍然互相攻击。否则,打印“NO”。
示例
输入 #1
2 2 2 1 2 2 1 3 1 2 2
输出 #1
NO YES
注意
在第一个测试用例中,车位于 $$$2 \times 2$$$ 棋盘的对角。他们每个人都可以移动到邻近的角落,但移动到那里意味着会受到另一辆车的攻击。
在第二个测试用例中,$$$3 \times 3$$$ 棋盘中间有一个车。它有 $$$4$$$ 有效动作,并且每个动作都很好,因为没有其他车可以攻击它。