9676 - 零件组装机

曾经发明了激光发生器的发明家 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)的无向边。

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

第一行一个整数 t ，表示有 t 组数据。

每组数据的第一行有两个整数 n，m，表示某个带标号的无向图有 n 个从 0 到 n - 1 标号的顶点，以及 m 条边。 接下来 m 行，每行两个整数 u,v ，表示一条从 u 到 v 的无向边。

对于每组数据，输出一行。如果这个无向图可以被零件制造机制造，输出 YES，否则输出 NO。

对于 5\% 的数据，图给定的图联通且 m = n - 1；
对于另 15\% 的数据，n \leq 5；
对于 50\% 的数据，n \leq 1000；
对于所有测试点，t \leq 10，n,m \leq 100000。

上海省选