CF1702E.Split Into Two Sets

Polycarp was recently given a set of $n$ (number $n$ — even) dominoes. Each domino contains two integers from $1$ to $n$.

Can he divide all the dominoes into two sets so that all the numbers on the dominoes of each set are different? Each domino must go into exactly one of the two sets.

For example, if he has $4$ dominoes: ${1, 4}$, ${1, 3}$, ${3, 2}$ and ${4, 2}$, then Polycarp will be able to divide them into two sets in the required way. The first set can include the first and third dominoes (${1, 4}$ and ${3, 2}$), and the second set — the second and fourth ones (${1, 3}$ and ${4, 2}$).

波利卡普最近得到了一组 $n$（$n$ 为偶数）个骨牌。每个骨牌包含两个取值范围为 $1$ 到 $n$ 的整数。

他能否将所有骨牌划分为两个集合，使得每个集合中所有骨牌上的数字互不相同？每个骨牌必须且仅能放入这两个集合中的一个。

例如，若他有 $4$ 个骨牌：${1, 4}$、${1, 3}$、${3, 2}$ 和 ${4, 2}$，则波利卡普能够以满足要求的方式将它们划分为两个集合。第一个集合可包含第一和第三个骨牌（${1, 4}$ 和 ${3, 2}$），第二个集合包含第二和第四个骨牌（${1, 3}$ 和 ${4, 2}$）。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The descriptions of the test cases follow.

The first line of each test case contains a single even integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of dominoes.

The next $n$ lines contain pairs of numbers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$) describing the numbers on the $i$-th domino.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

接下来是各测试用例的描述。

每个测试用例的第一行包含一个偶数 $n$（$2 \le n \le 2 \cdot 10^5$）—— 多米诺骨牌的数量。

接下来的 $n$ 行每行包含两个数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$），表示第 $i$ 张多米诺骨牌上的两个数字。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case print:

• YES, if it is possible to divide $n$ dominoes into two sets so that the numbers on the dominoes of each set are different;
• NO if this is not possible.

You can print YES and NO in any case (for example, the strings yEs, yes, Yes and YES will be recognized as a positive answer).

对每个测试用例，输出：

• YES，如果可以将 $n$ 个骨牌分成两组，使得每组中所有骨牌上的数字互不相同；
• NO，如果无法做到这一点。

YES 和 NO 的大小写不限（例如，字符串 yEs、yes、Yes 和 YES 均被视为肯定回答）。

In the first test case, the dominoes can be divided as follows:

• First set of dominoes: $[{1, 2}, {4, 3}]$
• Second set of dominoes: $[{2, 1}, {3, 4}]$

In other words, in the first set we take dominoes with numbers $1$ and $2$, and in the second set we take dominoes with numbers $3$ and $4$.

In the second test case, there's no way to divide dominoes into $2$ sets, at least one of them will contain repeated number.

在第一个测试用例中，多米诺骨牌可以按如下方式划分：

• 第一组多米诺骨牌：$[{1, 2}, {4, 3}]$
• 第二组多米诺骨牌：$[{2, 1}, {3, 4}]$

换言之，在第一组中我们选取编号为 $1$ 和 $2$ 的多米诺骨牌，而在第二组中我们选取编号为 $3$ 和 $4$ 的多米诺骨牌。

在第二个测试用例中，无法将多米诺骨牌划分为 $2$ 组，至少有一组会包含重复的数字。