题目描述

有一个 $n \times n$ 的国际象棋棋盘，上面放置了 $m$ 个车，满足以下条件：

• 没有两个车占据同一个格子；
• 没有两个车能够互相攻击。

一个车可以攻击其所在行或列的所有格子。

现在你可以选择恰好一个车，将其移动到另一个格子（可以选择移动哪一个车）。移动时，车可以沿着其所在的行或列移动到任意没有其他车阻挡的格子。

请判断是否存在一种移动方式，使得移动后依然没有任何两个车能够互相攻击。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 2000$），表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 8$），分别表示棋盘的大小和车的数量。

接下来的 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n$），表示第 $i$ 个车的位置：$x_i$ 表示行号，$y_i$ 表示列号。

保证没有两个车占据同一个格子，且没有两个车能够互相攻击。

输出格式

对于每个测试用例，如果存在一种方案可以移动恰好一个车到另一个格子，并且移动后依然没有任何两个车能够互相攻击，输出 "YES"；否则输出 "NO"。

说明/提示

在第一个测试用例中，两个车分别位于 $2 \times 2$ 棋盘的对角角落。每个车都可以移动到相邻的角落，但这样会被另一个车攻击。

在第二个测试用例中，只有一个车位于 $3 \times 3$ 棋盘的中央。它有 $4$ 个可行的移动，每次移动后都不会被其他车攻击。

由 ChatGPT 4.1 翻译

样例

2
2 2
1 2
2 1
3 1
2 2

NO
YES