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$$$组,其中至少有一个会包含重复的数字。