题目描述

多米诺骨牌给定 $n$ 个（$n$ 是偶数）。每个多米诺骨牌包含两个整数，这两个整数的范围从 $1$ 到 $n$。

他能将所有多米诺骨牌分成两组，以便每组骨牌上的数字都不同吗？每个多米诺骨牌必须恰好放入两个组中的一个。

例如，如果他有 $4$ 个多米诺骨牌：$\{1,4\}，\{1,3\}，\{3,2\}$ 和 $\{4,2\}$，那么光头强就能按要求将它们分成两组。第一组可以包括第一和第三个骨牌（$\{1,4\}$ 和 $\{3,2\}$），第二组可以包括第二和第四个骨牌（$\{1,3\}$ 和 $\{4,2\}$）。

输入格式

每个测试包含多组数据。

第一行包含一个整数 $t(1≤t≤10^4)$ — 表示测试用例的数量。

接下来是 $t$ 组测试数据。

每个测试用例的第一行包含一个偶数 $n(2≤n≤2⋅10^5)$ — 表示多米诺骨牌的数量。

接下来的 $n$ 行，每行包含两个数字 $a_i$ 和 $b_i(1≤a_i,b_i≤n)$，描述第 $i$ 张多米诺骨牌上的数字。

保证所有测试用例中 $n$ 的总和不超过 $2⋅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 的多米诺骨牌。

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