Chubby Trung and skinny Hanh are best friend. They are smart and lovely kids, and they are both very good at math and programming. One day, chubby Trung set a puzzle to challenge skinny Hanh. Trung gives a list of $n$ distinct points on a Cartesian coordinate plane to Hanh and asks Hanh to draw a single loop connecting all these points with some conditions:
The loop consists of exactly $n$ segments that are parallel to the axes.
Each segment’s two ends must be $2$ of the given points. Other than these $2$ points, the segment must not go through any other points from the list.
Two consecutive segments in the loop must be perpendicular (i.e. they must form a $90$ degree angle), and they must have exactly one intersection (which is at their common end).
The loop must go through all $n$ points. The first and last point of the loop must be the same.
The loop must not self-intersect.
In the following examples, the first figure shows a valid loop. The second figure shows an invalid loop because there are segments’ ends at $(2,2)$ which is not in the list. The third one is also invalid because it does not go through all $n$ points. And the last figure is also invalid because there exists $2$ consecutive segments that are not perpendicular.
Your task is to help skinny Hanh determine whether it is possible to create such loop.
The input starts with an positive integer $t$ – the number of test cases. Then $t$ test cases follow, each has the following format:
The first line consists of an integer $n$ – the number of points in the list ($1 \leq n \leq 2 \cdot 10^5$). The sum of $n$ in all test cases does not exceed $10^6$.
The $i$-th line of the next $n$ lines contains $2$ integers $x_ i$, $y_ i$ describing the $i$-th point ($0 \leq \lvert x_ i \rvert ,\lvert y_ i \rvert \leq 10^9$). It is guaranteed that no two points have the same coordinates.
For each test case, if it is possible to draw the loop, print ‘YES’; otherwise, print ‘NO’.
Sample Input 1 | Sample Output 1 |
---|---|
2 6 1 1 1 3 2 2 2 3 3 1 3 2 3 1 1 1 2 2 1 |
YES NO |
Sample Input 2 | Sample Output 2 |
---|---|
2 5 1 1 1 3 2 2 3 1 3 3 5 1 1 1 3 2 3 3 1 3 3 |
NO NO |