← 返回题目列表

Codeforces · 1702/E

E. 分为两组

中文机器翻译题面 查看原题

Polycarp 最近得到了一套 $$$n$$$(数量 $$$n$$$ — 偶数)多米诺骨牌。每个多米诺骨牌包含两个从 $$$1$$$ 到 $$$n$$$ 的整数。

他能否将所有多米诺骨牌分成两组,使得每组多米诺骨牌上的所有数字都不相同?每张多米诺骨牌必须恰好进入两组中的一组。

例如,如果他有 $$$4$$$ 多米诺骨牌:$$$\{1, 4\}$$$、$$$\{1, 3\}$$$、$$$\{3, 2\}$$$ 和 $$$\{4, 2\}$$$,那么 Polycarp 将能够按照要求的方式将它们分成两组。第一组可以包括第一张和第三张多米诺骨牌($$$\{1, 4\}$$$ 和 $$$\{3, 2\}$$$),第二组包括第二张和第四张多米诺骨牌($$$\{1, 3\}$$$ 和 $$$\{4, 2\}$$$)。

输入

第一行包含一个整数 $$$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、yes、Yes 和 YES 将被识别为肯定答案)。

示例

输入 #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

注意

在第一个测试用例中,多米诺骨牌可以划分如下:

- 第一组多米诺骨牌:$$$[\{1, 2\}, \{4, 3\}]$$$
- 第二组多米诺骨牌:$$$[\{2, 1\}, \{3, 4\}]$$$

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