311204: CF1949H. Division Avoidance

H. Division Avoidancetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

A newly discovered organism can be represented as a set of cells on an infinite grid. There is a coordinate system on the grid such that each cell has two integer coordinates $x$ and $y$. A cell with coordinates $x=a$ and $y=b$ will be denoted as $(a, b)$.

Initially, the organism consists of a single cell $(0, 0)$. Then zero or more divisions can happen. In one division, a cell $(a, b)$ is removed and replaced by two cells $(a+1, b)$ and $(a, b+1)$.

For example, after the first division, the organism always consists of two cells $(1, 0)$ and $(0, 1)$, and after the second division, it is either the three cells $(2, 0)$, $(1, 1)$ and $(0, 1)$, or the three cells $(1, 0)$, $(1, 1)$ and $(0, 2)$.

A division of a cell $(a, b)$ can only happen if the cells $(a+1, b)$ and $(a, b+1)$ are not yet part of the organism. For example, the cell $(1, 0)$ cannot divide if the organism currently consists of the three cells $(1, 0)$, $(1, 1)$ and $(0, 2)$, since the cell $(1, 1)$ that would be one of the results of this division is already part of the organism.

You are given a set of forbidden cells ${(c_i, d_i)}$. Is it possible for the organism to contain none of those cells after zero or more divisions?

Input

Each test contains multiple test cases. The first line contains an integer $t$ ($1 \le t \le 10\,000$) — the number of test cases. The descriptions of the $t$ test cases follow.

The first line of each test case contains an integer $n$ ($1 \le n \le 10^6$) — the number of forbidden cells.

The next $n$ lines contain two integers each. The $i$-th of such lines contains $c_i$ and $d_i$ ($0 \le c_i, d_i \le 10^9$) — the coordinates of the $i$-th forbidden cell. It is guaranteed that all forbidden cells are distinct.

It is guaranteed that the sum of values of $n$ over all test cases does not exceed $10^6$.

Output

For each test case, print $\texttt{YES}$ if it is possible for the organism to contain no forbidden cells after zero or more divisions. Otherwise, print $\texttt{NO}$.

ExampleInput

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

Output

YES
NO

Note

In the first test case, dividing the following cells in the following order creates an organism without any forbidden cells: $(0, 0)$, $(1, 0)$, $(1, 1)$, $(0, 1)$, $(2, 1)$, $(2, 2)$, $(1, 2)$, $(1, 1)$. The following picture demonstrates how the organism changes during this process:

In the second test case, you can see that, surprisingly, any organism always has at least one cell in the $0 \le x, y \le 3$ square, no matter how many divisions we do.

题目大意：
这个题目是关于一个在无限网格上表示的新生物体。网格上有坐标系统，每个细胞都有两个整数坐标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, b)的分裂只能发生在细胞(a+1, b)和(a, b+1)尚未成为生物体的一部分的情况下。例如，如果生物体目前由三个细胞(1, 0)、(1, 1)和(0, 2)组成，那么细胞(1, 0)不能分裂，因为这将产生的细胞(1, 1)已经是生物体的一部分。

你得到了一组禁止的细胞{(c_i, d_i)}。在零次或多次分裂后，生物体是否可能不包含这些细胞？

输入输出数据格式：
输入：
每个测试包含多个测试案例。第一行包含一个整数t（1≤t≤10,000）——测试案例的数量。接下来是t个测试案例的描述。

每个测试案例的第一行包含一个整数n（1≤n≤10^6）——禁止的细胞的数量。

接下来的n行每行包含两个整数。第i行包含c_i和d_i（0≤c_i, d_i≤10^9）——第i个禁止细胞的坐标。保证所有禁止的细胞都是不同的。

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

输出：
对于每个测试案例，如果生物体在零次或多次分裂后可能不包含禁止的细胞，打印YES。否则，打印NO。

示例：
输入：
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
输出：
YES
NO

注意：
在第一个测试案例中，按照以下顺序分裂以下细胞会产生一个没有禁止细胞的生物体：(0, 0)、(1, 0)、(1, 1)、(0, 1)、(2, 1)、(2, 2)、(1, 2)、(1, 1)。下图展示了在这个过程中生物体是如何变化的。

在第二个测试案例中，你可以看到，无论我们进行多少次分裂，任何生物体总是至少有一个细胞在0≤x, y≤3的正方形内，这是令人惊讶的。题目大意： 这个题目是关于一个在无限网格上表示的新生物体。网格上有坐标系统，每个细胞都有两个整数坐标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, b)的分裂只能发生在细胞(a+1, b)和(a, b+1)尚未成为生物体的一部分的情况下。例如，如果生物体目前由三个细胞(1, 0)、(1, 1)和(0, 2)组成，那么细胞(1, 0)不能分裂，因为这将产生的细胞(1, 1)已经是生物体的一部分。 你得到了一组禁止的细胞{(c_i, d_i)}。在零次或多次分裂后，生物体是否可能不包含这些细胞？ 输入输出数据格式： 输入： 每个测试包含多个测试案例。第一行包含一个整数t（1≤t≤10,000）——测试案例的数量。接下来是t个测试案例的描述。 每个测试案例的第一行包含一个整数n（1≤n≤10^6）——禁止的细胞的数量。 接下来的n行每行包含两个整数。第i行包含c_i和d_i（0≤c_i, d_i≤10^9）——第i个禁止细胞的坐标。保证所有禁止的细胞都是不同的。 保证所有测试案例中n的值的总和不超过10^6。 输出： 对于每个测试案例，如果生物体在零次或多次分裂后可能不包含禁止的细胞，打印YES。否则，打印NO。 示例： 输入： 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 输出： YES NO 注意： 在第一个测试案例中，按照以下顺序分裂以下细胞会产生一个没有禁止细胞的生物体：(0, 0)、(1, 0)、(1, 1)、(0, 1)、(2, 1)、(2, 2)、(1, 2)、(1, 1)。下图展示了在这个过程中生物体是如何变化的。 在第二个测试案例中，你可以看到，无论我们进行多少次分裂，任何生物体总是至少有一个细胞在0≤x, y≤3的正方形内，这是令人惊讶的。