ICPC Vietnam National Programming Contest 2020 - Open

Start

2020-11-14 21:00 AKST

ICPC Vietnam National Programming Contest 2020 - Open

End

2020-11-15 02:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -250 days 22:12:18

Time elapsed

5:00:00

Time remaining

0:00:00

Problem L
Looping Around

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.

\includegraphics[width=.8\textwidth ]{images/all.png}

Your task is to help skinny Hanh determine whether it is possible to create such loop.

Input

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.

Output

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