P16009 [CCO 2016 Day 1] Legends 神话

加拿大是由一张城市和道路组成的网络构成的国家。每条道路都可以双向通行。通过这些道路，可以从任意一个城市到达另一个城市。 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$ 解释 |测试用例编号|网络结构|说明 | |:----:|:--:|:-----:| |$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。