CF1702E Split Into Two Sets

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 和 NO（例如 yEs、yes、Yes 和 YES 都被认为是肯定答案）。

在第一个测试用例中，骨牌可以这样分组： - 第一组骨牌：$[\{1, 2\}, \{4, 3\}]$ - 第二组骨牌：$[\{2, 1\}, \{3, 4\}]$ 换句话说，在第一组中我们取编号为 $1$ 和 $2$ 的骨牌，在第二组中取编号为 $3$ 和 $4$ 的骨牌。 在第二个测试用例中，无法将骨牌分成 $2$ 个集合，至少有一个集合会包含重复的数字。 由 ChatGPT 4.1 翻译