[SHOI2015] 零件组装机
题目描述
曾经发明了激光发生器的发明家 SHTSC 又公开了他的新发明:零件组装机——一种可以生产并组装零件的神秘装置。
一个零件是一张顶点由 $0$ 到 $n-1$ 标号的无向图,零件组装机有以下两种功能:
1. 生产一个仅有一个顶点标号为$0$而没有边的零件。
2. 组合两个已有的零件 $G_1$、$G_2$ ,且 $G_2$ 的顶点数 $m$ 大于等于 $G_1$ 的顶点数 $n$ ,得到新的零件 $G$ 。$G$ 的顶点集合是 $G_1,G_2$ 顶点集合的并集,并且 $G_2$ 的顶点 $i(0\leq i < m)$ 被重新标号为 $n+i$ 。$G$ 的边集是 $G_1,G_2$边集的并集再对所有标号为 $a(a \geq n)$ 的顶点添加一条连接$(a,a \mod n)$的无向边。
![](https://cdn.luogu.com.cn/upload/pic/17059.png)
现在 SHTSC 正在思考,对于一个给定的零件,能否由零件组装机生产组装得到。注意:零件是带标号的,这意味着两个零件即使仅有标号不同也被视为不同的零件。为了帮助你理解问题,SHTSC 特地给了你顶点数 $\le 5$的所有零件的图例。
![](https://cdn.luogu.com.cn/upload/pic/17060.png)
输入输出格式
输入格式
第一行一个整数 $t$ ,表示有 $t$ 组数据。
每组数据的第一行有两个整数 $n$,$m$,表示某个带标号的无向图有 $n$ 个从 $0$ 到 $n - 1$ 标号的顶点,以及 $m$ 条边。 接下来 $m$ 行,每行两个整数 $u,v$ ,表示一条从 $u$ 到 $v$ 的无向边。
输出格式
对于每组数据,输出一行。如果这个无向图可以被零件制造机制造,输出 YES,否则输出 NO。
输入输出样例
输入样例 #1
3
1 0
2 0
4 6
0 1
0 2
1 2
1 3
2 3
3 0
输出样例 #1
YES
NO
YES
说明
对于 $5\%$ 的数据,图给定的图联通且 $m = n - 1$;
对于另 $15\%$ 的数据,$n \leq 5$;
对于 $50\%$ 的数据,$n \leq 1000$;
对于所有测试点,$t \leq 10$,$n,m \leq 100000$。