CF1949H.Division Avoidance

一种新发现的生物可以表示为无限网格上的一组细胞。网格上有一个坐标系，每个细胞有两个整数坐标 $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$）——表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^6$）——表示禁止出现的细胞数量。

接下来的 $n$ 行，每行包含两个整数 $c_i$ 和 $d_i$（$0 \le c_i, d_i \le 10^9$），表示第 $i$ 个禁止出现的细胞的坐标。保证所有禁止出现的细胞互不相同。

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

对于每个测试用例，如果存在一种分裂方式使得生物体不包含任何禁止出现的细胞，输出 $\texttt{YES}$；否则输出 $\texttt{NO}$。

在第一个测试用例中，按照如下顺序分裂细胞，可以得到一个不包含任何禁止出现细胞的生物体：$(0, 0)$、$(1, 0)$、$(1, 1)$、$(0, 1)$、$(2, 1)$、$(2, 2)$、$(1, 2)$、$(1, 1)$。下图展示了生物体在此过程中如何变化：

在第二个测试用例中，可以发现，无论如何分裂，生物体总会至少包含一个位于 $0 \le x, y \le 3$ 的细胞。

由 ChatGPT 4.1 翻译