题目描述

译自 CCO 2016 Day1 T3「Legends」。

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

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

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

• 在两个原本没有直接相连的城市之间修建一条道路。
• 建立一座新城市。刚建立的新城市一开始不会和任何现有城市相连。
• 城市 $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
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 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
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
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
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$。