P15775 [JAG 2025 Summer Camp #2] Hanako' s Art II

There are $2n$ points in the $xy$-plane. Any two points have neither the same $x$-coordinate nor the same $y$-coordinate. Each point has a color represented by an integer between $1$ and $n$ (inclusive). For each of the $n$ colors, there are exactly two points of that color. An artist, Hanako, is willing to create a masterpiece by drawing $n$ polygonal chains in the $xy$-plane. According to her aesthetic sense, a masterpiece must satisfy all the following conditions. - Any two points having the same color are the endpoints of one of the polygonal chains. - Each polygonal chain consists of exactly two line segments, each of which is parallel to the $x$- or $y$-axis. - No two polygonal chains intersect. Your task is to determine whether Hanako can create such a masterpiece.

The input consists of multiple test cases. The first line of input contains an integer $t$ ($1 \leq t \leq 50\,000$) representing the number of test cases. After that, $t$ test cases follow. Each of them is given in the following format. $$ \begin{aligned} & n \\ & y_1 \ c_1 \\ & \vdots \\ & y_{2n} \ c_{2n} \end{aligned} $$ The first line contains an integer $n$ ($1 \leq n \leq 1\,000$) representing the number of polygonal chains which Hanako has to draw. Each of the following $2n$ lines contains two integers $y_i$ and $c_i$ satisfying $1 \leq y_i \leq 2n$ and $1 \leq c_i \leq n$. Each line represents that the $i$-th point has the coordinate $(i, y_i)$ and the color $c_i$. It is guaranteed that $y_i \neq y_j$ if $i \neq j$. In addition, no three points have the same color. The sum of $n^2$ over all the test cases does not exceed $10^6$.

If Hanako can create a masterpiece, print "Yes"; otherwise, print "No".

One of the possible masterpieces in Sample Input 1 is depicted in Figure J-1. :::align{center}  Figure J-1: Illustration of Sample Input 1 :::