Problem 3. Point Elimination

USACO 2026 Third Contest, Silver

You have $N$ ($2 \leq N \leq 10^5, N$ is even$)$ points $(x_i,y_i)$ ($1 \leq x_i, y_i \leq 10^6$) on an infinite 2D-coordinate plane.

You can perform the following two types of operations any number of times:

• Choose two points that are directly adjacent to each other (manhattan distance of $1$), and remove both points.
• Choose any two points and swap their y-coordinates. Formally, points $(a,b)$ and $(c,d)$ become $(a,d)$ and $(c,b)$ respectively.

Determine if it is possible to eliminate all points on the board. Note that it may be the case that two points may map to the same coordinate; they should still be treated as different points. You also may not directly delete points on the same coordinate, as they are technically not directly adjacent.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains $T$ ($1 \leq T \leq 5000$), the number of test cases.

The first line of each test case contains an integer $N$.

The following $N$ lines contain two integers $x_i$ and $y_i$.

It is guaranteed that the sum of $N$ over all test cases does not exceed $5\cdot 10^5$.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, output "YES" or "NO" on a new line.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

NO
YES
YES
NO

For the first test, the only two points are equal, so no swaps will do anything. Thus, our answer is NO.

In the second test, we can swap the y-coordinates of 6 and 7 with 8 and 8. Then, we can remove the first two points (horizontal adjacency) and the last two (vertical).

For the third test, no swaps are needed. We can remove the first pair, second, and third.

In the last test, it can be shown that no matter how we swap the y-coordinates, we will never be able to remove all the points in adjacent pairs.

SCORING: Input 2: $T\le 1000$, $N \le 6$Inputs 3-5: $N\le 100$Inputs 6-11: No additional constraints.

Problem credits: Alex Pylypenko, Chongtian Ma