Split Into Two Sets

题意翻译

给你 $n$ （$n$ 为偶数，$2 \le 2 \cdot 10^5$）个，数对。数对中的每个数字都是从 $1$ 到 $n$ 的。 现在问你是否能将这些数对分到两个集合中。使得每个集合中没有任何一个重复的数字。 比如有下面这四个数对：$\{1, 4\}, \{1, 3\}, \{3, 2\}, \{4, 2\}$。 那么可以这样分配这些数对： - 第一个集合包含数对 $\{1, 4\}$ 和 $\{3, 2\}$。第二个包含 $\{1, 3\}$ 和 $\{4, 2\}$。 由 [tzyt](https://www.luogu.com.cn/user/394488) 翻译

题目描述

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\} $ ).

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

6
4
1 2
4 3
2 1
3 4
6
1 2
4 5
1 3
4 6
2 3
5 6
2
1 1
2 2
2
1 2
2 1
8
2 1
1 2
4 3
4 3
5 6
5 7
8 6
7 8
8
1 2
2 1
4 3
5 3
5 4
6 7
8 6
7 8

输出样例 #1

YES
NO
NO
YES
YES
NO

说明

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.

题目大意：
给定一个偶数 $n$（$2 \le n \le 2 \cdot 10^5$），和 $n$ 个数对。每个数对中的数字都来自 $1$ 到 $n$。要求判断是否可以将这些数对分成两个集合，使得每个集合中不含有重复的数字。

输入输出数据格式：
输入格式：
- 第一行包含一个整数 $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$。

输出格式：
- 对于每个测试用例，如果可以将 $n$ 个多米诺骨牌分成两个符合要求的集合，则输出 YES；否则输出 NO。
- YES 和 NO 的大小写不敏感。题目大意： 给定一个偶数 $n$（$2 \le n \le 2 \cdot 10^5$），和 $n$ 个数对。每个数对中的数字都来自 $1$ 到 $n$。要求判断是否可以将这些数对分成两个集合，使得每个集合中不含有重复的数字。 输入输出数据格式： 输入格式： - 第一行包含一个整数 $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$。 输出格式： - 对于每个测试用例，如果可以将 $n$ 个多米诺骨牌分成两个符合要求的集合，则输出 YES；否则输出 NO。 - YES 和 NO 的大小写不敏感。