#P4594. [Shoi2015]零件组装机
[Shoi2015]零件组装机
[SHOI2015] 零件组装机
题目描述
曾经发明了激光发生器的发明家 SHTSC 又公开了他的新发明:零件组装机——一种可以生产并组装零件的神秘装置。
一个零件是一张顶点由 到 标号的无向图,零件组装机有以下两种功能:
- 生产一个只有顶点 、没有边的零件。
- 取顶点数分别为 的两个零件 ,其中 。保留 的编号,把 中原编号 改为 。保留两件内部的所有边,并对每个新编号 添加一条连接 与 的无向边。

现在 SHTSC 正在思考,对于一个给定的零件,能否由零件组装机生产组装得到。注意:零件是带标号的,这意味着两个零件即使仅有标号不同也被视为不同的零件。为了帮助你理解问题,SHTSC 特地给了你顶点数 的所有零件的图例。

输入格式
第一行一个整数 ,表示有 组数据。
每组数据的第一行有两个整数 ,,表示某个带标号的无向图有 个从 到 标号的顶点,以及 条边。 接下来 行,每行两个整数 ,表示一条连接 与 的无向边,。输入可以含自环或重复的边。判断输入的图能否原样由组装机得到。
输出格式
对于每组数据,输出一行。如果这个无向图可以被零件制造机制造,输出 YES,否则输出 NO。
3
1 0
2 0
4 6
0 1
0 2
1 2
1 3
2 3
3 0
YES
NO
YES
数据范围
对于 的数据,给定的图连通且 ; 对于另 的数据,; 对于 的数据,; 对于所有测试点,,,。