题目描述

Polycarp 最近得到了一组多米诺骨牌，骨牌数量 $n$ 为偶数。每张骨牌的两端各写着一个 $1$ 到 $n$ 之间的整数。

Polycarp 想把全部骨牌恰好分成两个集合，每张骨牌必须进入且只能进入其中一个集合。他要求在任意一个集合中，写在所有骨牌端点上的数字都互不相同；也就是说，同一个数字不能在同一集合中出现两次，即使这两次出现在同一张骨牌的两端也不允许。

例如，四张骨牌 $\{1,4\}$、$\{1,3\}$、$\{3,2\}$、$\{4,2\}$ 可以完成分组：第一组放第一、三张，第二组放第二、四张，两组内部都没有重复数字。

题目包含多组测试。请判断每组骨牌能否满足上述分组要求。

输入格式

第一行包含整数 $t$，表示测试用例数量。

每个测试用例先输入一个偶数 $n$，表示骨牌数量；接下来 $n$ 行，每行包含两个整数 $a_i,b_i$，表示第 $i$ 张骨牌两端的数字。

输出格式

对于每个测试用例输出一行。若存在合法分组，输出 YES；否则输出 NO。答案字母可以使用任意大小写组合。

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

2
2
1 2
2 1
2
1 1
1 2

YES
NO

样例说明 #2

第一组可以把两张反向骨牌分开；第二组含有两端相同的骨牌，无法满足要求。

1
4
1 2
2 3
3 4
4 1

YES

样例说明 #3

四张骨牌构成偶环，可以沿环交替放入两组。

数据范围与约定

$1\le t\le 10^4$，$2\le n\le 2\times 10^5$ 且 $n$ 为偶数，$1\le a_i,b_i\le n$。所有测试用例中 $n$ 的总和不超过 $2\times 10^5$。