---

题目描述

译自 CCO 2016 Day1 T3「Legends」。

加拿大由许多城市和道路组成，每条路都可以双向通行。从任意一个城市都能通过这些道路到达另一个城市。

苏茜研究加拿大人的创世神话。她特别感兴趣于五个神话（对应这个问题的五个子任务）。这些神话非常相似，每个神话都有如下的结构：

一开始，加拿大的道路网络有着特定的布局。随着时间的推移，为了满足不断增长的人口需求，道路网络发生了变化。每次变化有以下两种形式：

1. 在两个原本没有直接相连的城市之间修建一条道路。
2. 建立一座新城市。刚建立的新城市一开始不会和任何现有城市相连。

   • 城市 $u$ 增长过大，被分割成两个城市 $v$ 和 $w$。原本直接与 $u$ 通过道路相连的城市被划分为集合 $A$ 和 $B$。从 $A$ 中的每个城市到 $v$，从 $B$ 中的每个城市到 $w$，以及从 $v$ 到 $w$ 都建造了一条道路。

   • 例如，

     变成了：

五个神话的区别在于它们描述的初始道路网络结构不同。以下是每个神话中的原始结构：

• 子任务 1（烧瓶神话）：

• 子任务 2（月亮神话）： 。

• **子任务 3（太阳神话）

• 子任务 4（鹰爪神话）：

• 子任务 5（狐狸神话）：

对于每个子任务，你必须根据加拿大的布局输入，确定这个神话是否可能是真实的。

---

输入格式

第一行包含一个整数 $S$，表示你需要解决的子任务。
第二行包含一个整数 $T$，表示数据组数。
每组输入数据由一个空行隔开，接着是两个整数 $N, M$，分别表示城市和道路的数量。城市编号从 $1$ 到 $N$。
接下来 $M$ 行，每行包含两个整数 $a,b$，表示由道路连接的两个城市。
没有道路连接一个城市到自身。没有两条道路连接同一对城市。可以通过这些道路从任何一个城市到达另一个城市。

---

输出格式

对于每组输入数据，输出一行一个字符串 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

输出

YES
NO

第 1 组数据

解释：符合烧瓶神话。

第 2 组数据

解释：不符合烧瓶神话。

---

样例 2

输入

2
2

2 1
1 2

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

输出

NO
YES

第 1 组数据

解释：不符合月亮神话。

第 2 组数据

解释：符合月亮神话，因为我们可以在由城市 $1,2,3$ 形成的月亮上添加城市 $4$ 和 $5$ 以及一些额外的道路。

---

样例 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

输出

YES
YES

第 1 组数据

解释：符合太阳神话，在城市 $1,2,3,4$ 上。

第 2 组数据

解释：符合太阳神话，在城市 $1,2,3,4$ 之间插入了一些新城市。

---

样例 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

输出

NO
YES

第 1 组数据

解释：不符合鹰爪神话。

第 2 组数据

解释：符合鹰爪神话，在城市 $1,2,4,6$ 上。

---

样例 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

输出

NO
YES

第 1 组数据

解释：不符合狐狸神话。

第 2 组数据

解释：符合狐狸神话，在城市 $1,2,4,5,6$ 上。

---

数据范围与提示

• 在子任务 3中，所有输入数据组的 $N$ 之和最多为 $10^{5}$，所有输入数据组的 $M$ 之和最多为 $10^{5}$。
• 在所有其他子任务中，所有输入数据组的 $N$ 之和最多为 $1000$，所有输入数据组的 $M$ 之和最多为 $1000$。
• 对于 $100\%$ 的数据，$1 \leq S \leq 5$，$T \geq 1$，$2 \leq N$，$1 \leq M$，$1 \leq a, b \leq N$。

---