题目描述

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".

2
3
2 1
1 2
4 3
6 1
3 3
5 2
3
2 3
6 1
5 2
1 1
4 3
3 2

Yes
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 :::