题目描述

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 都被认为是肯定答案）。

样例

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

YES
NO
NO
YES
YES
NO

提示

样例解释

在第一个测试用例中，骨牌可以这样分组：

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

换句话说，在第一组中我们取编号为 $1$ 和 $2$ 的骨牌，在第二组中取编号为 $3$ 和 $4$ 的骨牌。

在第二个测试用例中，无法将骨牌分成 $2$ 个集合，至少有一个集合会包含重复的数字。