说明

你有一个无限大的二维坐标平面，上面有 $N$（$2 \leq N \leq 10^5$，$N$ 为偶数）个点 $(x_i, y_i)$（$1 \leq x_i, y_i \leq 10^6$）。

你可以执行以下两种操作任意次：

• 选择两个彼此直接相邻的点（曼哈顿距离为 $1$），并将这两个点移除。
• 选择任意两个点并交换它们的纵坐标。形式化地，点 $(a, b)$ 和 $(c, d)$ 分别变为 $(a, d)$ 和 $(c, b)$。

判断是否有可能消除棋盘上的所有点。注意，可能存在两个点坐标相同的情况；它们仍应被视为不同的点。你也不能直接删除相同坐标上的点，因为严格来说它们并不直接相邻。

输入格式

第一行包含 $T$（$1 \leq T \leq 5000$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $N$。

接下来的 $N$ 行每行包含两个整数 $x_i$ 和 $y_i$。

保证所有测试用例的 $N$ 之和不超过 $5 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行 "YES" 或 "NO"。

4
2
1 1
1 1
4
6 10
7 11
8 1
8 1
6
1 2
1 3
1 4
1 5
10 10
11 10
6
1 1
1 1
1 1
1 1
10 10
11 11

NO
YES
YES
NO

提示

对于第一个测试，仅有的两个点相同，因此交换操作无法改变任何东西。所以答案是 NO。

在第二个测试中，我们可以将点 $(6,10)$ 和 $(7,11)$ 的纵坐标分别与点 $(8,1)$ 和 $(8,1)$ 的纵坐标交换。然后，我们可以移除前两个点（水平相邻）和后两个点（垂直相邻）。

对于第三个测试，无需交换。我们可以依次移除第一对、第二对和第三对。

在最后一个测试中，可以证明无论我们如何交换纵坐标，都无法将所有点按相邻对移除。

评分标准

• 输入 2：$T \le 1000$，$N \le 6$
• 输入 3-5：$N \le 100$
• 输入 6-11：无额外限制。

题目来源：Alex Pylypenko, Chongtian Ma

翻译由 DeepSeek 完成