题目描述

加拿大是由一张城市和道路组成的网络构成的国家。每条道路都可以双向通行。通过这些道路，可以从任意一个城市到达另一个城市。

Suzie 正在研究加拿大人的创世神话。她特别关注五个神话（对应本题的五个子任务）。这些神话非常相似。每个神话的内容大致如下：

最初，加拿大的道路网络有一个特定的结构。随着时间推移，网络不断被修改以满足日益增长的人口需求。每次修改都属于以下几种情况之一：

• 在两个尚未直接相连的城市之间修建了一条新路。
• 新建了一个城市。通过这种方式建成的城市最初没有和任何已有城市相连。
• 某个城市 $u$ 规模过大，被拆分成两个城市 $v$ 和 $w$。原本直接和 $u$ 相连的城市被分成两组 $A$ 和 $B$。接着，从 $A$ 中的每个城市修建道路到 $v$，从 $B$ 中的每个城市修建道路到 $w$，以及从 $v$ 到 $w$ 也修建了道路。例如，

变成

这五个神话只在加拿大最初的结构上有所不同。以下是每个神话所描述的原始结构：

子任务1【瓶子神话】	子任务2【月亮神话】
子任务3【太阳神话】	子任务4【鹰爪神话】
子任务5【狐狸神话】	<

对于每个子任务，你需要输入加拿大当前的布局，判断该神话是否有可能成立。

每个子任务满分 $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$ 的总和不超过 $1\,000$。

$M$ 也满足同样的条件。特别地，子任务 $3$ 中所有测试用例中 $M$ 的总和不超过 $10^5$，其他子任务中所有测试用例中 $M$ 的总和不超过 $1\,000$。

输出格式

对于每个测试用例，输出一行，内容为 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

2
2

2 1
1 2

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

NO
YES

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

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

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$ 解释

测试用例编号	网络结构	说明
$1$		符合瓶子神话
$2$		不符合瓶子神话

样例 $2$ 解释

测试用例编号	网络结构	说明
$1$		不符合月亮神话
$2$		符合月亮神话，因为我们可以在由城市 $1$、$2$、$3$ 组成的月亮结构上添加城市4和5及一些额外道路。

样例 $3$ 解释

测试用例编号	网络结构	说明
$1$		符合太阳神话，涉及城市 $1$、$2$、$3$ 和 $4$
$2$		符合太阳神话，涉及城市 $1$、$2$、$3$ 和 $4$，其中一些新城市插入在城市 $1$ 和 $4$ 之间

样例 $4$ 解释

测试用例编号	网络结构	说明
$1$		不符合鹰爪神话
$2$		符合鹰爪神话，涉及城市 $1$、$2$、$4$ 和 $6$

样例 $5$ 解释

测试用例编号	网络结构	说明
$1$		不符合狐狸神话
$2$		符合狐狸神话，涉及城市 $1$、$2$、$4$、$5$ 和 $6$

翻译来源：GPT 4.1 mini。