P15575 [USACO26FEB] Point Elimination S

你有一个无限大的二维坐标平面，上面有 $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"。

对于第一个测试，仅有的两个点相同，因此交换操作无法改变任何东西。所以答案是 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 完成