← 返回题目列表

Codeforces · 1949/H

H. 除法避免

中文机器翻译题面 查看原题

新发现的生物体可以表示为无限网格上的一组细胞。网格上有一个坐标系,每个单元格都有两个整数坐标 $$$x$$$ 和 $$$y$$$。坐标为 $$$x=a$$$ 和 $$$y=b$$$ 的单元格将表示为 $$$(a, b)$$$。

最初,生物体由单个细胞 $$$(0, 0)$$$ 组成。然后可能会发生零个或多个除法。在一次分裂中,一个单元格 $$$(a, b)$$$ 被删除并替换为两个单元格 $$$(a+1, b)$$$ 和 $$$(a, b+1)$$$。

例如,第一次分裂后,生物体始终由两个细胞 $$$(1, 0)$$$ 和 $$$(0, 1)$$$ 组成,第二次分裂后,要么是三个细胞 $$$(2, 0)$$$、$$$(1, 1)$$$ 和 $$$(0, 1)$$$,要么是三个细胞 $$$(1, 0)$$$、$$$(1, 1)$$$ 和 $$$(0, 2)$$$。

仅当细胞 $$$(a+1, b)$$$ 和 $$$(a, b+1)$$$ 尚未成为生物体的一部分时,细胞 $$$(a, b)$$$ 才会发生分裂。例如,如果生物体当前由三个细胞 $$$(1, 0)$$$、$$$(1, 1)$$$ 和 $$$(0, 2)$$$ 组成,则细胞 $$$(1, 0)$$$ 无法分裂,因为作为此分裂结果之一的细胞 $$$(1, 1)$$$ 已经是生物体的一部分。

给你一组禁止单元格$$${(c_i, d_i)}$$$。有机体有可能在零次或多次分裂后不再含有这些细胞吗?

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10\,000$$$) — 测试用例的数量。 $$$t$$$ 测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$) — 禁止单元格的数量。

接下来的 $$$n$$$ 行每行包含两个整数。这些行的第 $$$i$$$ 包含 $$$c_i$$$ 和 $$$d_i$$$ ($$$0 \le c_i, d_i \le 10^9$$$) — 第 $$$i$$$ 个禁止单元格的坐标。保证所有禁止单元都是不同的。

保证所有测试用例的$$$n$$$值的总和不超过$$$10^6$$$。

输出

对于每个测试用例,如果有机体在零次或多次分裂后可能不包含禁止细胞,则打印 $$$\texttt{YES}$$$。否则,打印 $$$\texttt{NO}$$$。

示例

输入 #1

2
4
0 0
1 0
0 1
1 1
16
0 0
0 1
0 2
0 3
1 0
1 1
1 2
1 3
2 0
2 1
2 2
2 3
3 0
3 1
3 2
3 3

输出 #1

YES
NO

注意

在第一个测试用例中,按以下顺序划分以下单元格创建一个没有任何禁止单元格的有机体:$$$(0, 0)$$$, $$$(1, 0)$$$, $$$(1, 1)$$$, $$$(0, 1)$$$, $$$(2, 1)$$$, $$$(2, 2)$$$, $$$(1, 2)$$$, $$$(1, 1)$$$。下图展示了生物体在这个过程中是如何变化的:

在第二个测试用例中,您可以令人惊讶地看到,任何生物体在 $$$0 \le x, y \le 3$$$ 正方形中始终至少有一个细胞,无论我们进行多少次分裂。