You have N (2≤N≤105,N is even) points (xi,yi)(1≤xi,yi≤106) 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≤T≤5000), the number of test cases.
The first line of each test case contains an integer N.
The following N lines contain two integers xi and yi.
It is guaranteed that the sum of N over all test cases does not exceed 5⋅105.
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≤1000, N≤6
Inputs 3-5: N≤100
Inputs 6-11: No additional constraints.
Problem credits: Alex Pylypenko, Chongtian Ma