Canadia 的国家由一个城市和道路组成的网络构成。每条道路都可以双向通行。通过这些道路，可以从任何一个城市到达其他任何城市。

Suzie 正在研究 Canadia 人民的创世神话。她对五个神话特别感兴趣（这五个神话分别对应本题的五个子任务）。这些神话非常相似。每个神话都具有以下形式：

起初，Canadia 的道路网络具有特定的结构。随着时间的推移，为了满足 Canadia 不断增长的人口需求，网络进行了修改。每次修改都属于以下形式之一：

• 在两个尚未有直接道路连接的城市之间修建了一条道路。
• 新建了一座城市。以这种方式建造的城市最初不与任何现有城市相连。
• 城市 $u$ 变得过大，被拆分为两座城市 $v$ 和 $w$。原本直接与 $u$ 相连的城市被划分为集合 $A$ 和 $B$。修建从集合 $A$ 中的每个城市到 $v$ 的道路，从集合 $B$ 中的每个城市到 $w$ 的道路，以及从 $v$ 到 $w$ 的道路。例如：

这五个神话的区别仅在于它们认为 Canadia 最初的结构。根据每个神话，原始结构如下：

子任务 1 [烧瓶神话]	子任务 2 [月亮神话]
子任务 3 [太阳神话]	子任务 4 [鹰爪神话]
子任务 5 [狐狸神话]

对于每个子任务，你必须将 Canadia 的布局作为输入，并确定该神话是否可能是正确的。

每个子任务得 5 分。

输入格式

第一行包含一个整数 $S$ ($1 \le S \le 5$)，表示你必须解决的子任务。第二行包含一个整数 $T$ ($1 \le T$)，表示测试用例的数量。每个测试用例包含一个空行，随后是两个整数 $N$ 和 $M$ ($2 \le N, 1 \le M$)，分别表示城市和道路的数量。城市编号从 $1$ 到 $N$。接下来有 $M$ 行，每行包含两个整数 $a$ 和 $b$ ($1 \le a, b \le N$)，表示两个城市之间有一条道路。没有道路连接城市自身。没有两条道路连接同一对城市。可以通过道路从任何城市到达其他任何城市。

在子任务 3 中，你可以假设所有测试用例的 $N$ 之和最多为 $10^5$。在所有其他子任务中，所有测试用例的 $N$ 之和最多为 $1000$。

同样的条件适用于 $M$。特别地，在子任务 3 中，你可以假设所有测试用例的 $M$ 之和最多为 $10^5$。在所有其他子任务中，所有测试用例的 $M$ 之和最多为 $1000$。

输出格式

对于每个测试用例，输出一行，包含字符串 YES 或 NO。

样例

输入格式 1

1
2

4 5
1 2
2 3
3 4
1 3
2 4

7 8
1 2
2 3
3 4
4 1
4 5
5 6
6 7
7 4

输出格式 1

YES
NO

输入格式 2

2
2

2 1
1 2

5 6
1 3
5 1
2 3
4 5
1 2
3 5

输出格式 2

NO
YES

输入格式 3

3
2

7 8
1 2
2 3
3 4
4 1
4 5
5 6
6 7
7 4

8 8
1 2
2 3
3 4
4 5
5 6
6 1
7 3
8 7

输出格式 3

YES
YES

输入格式 4

4
2

4 4
1 2
2 3
3 4
4 1

6 6
1 2
2 3
1 4
4 5
2 4
1 6

输出格式 4

NO
YES

输入格式 5

5
2

5 5
1 2
2 3
2 4
4 5
3 5

6 6
1 2
2 3
1 4
4 5
2 4
1 6

输出格式 5

NO
YES