题目描述

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

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

输入格式

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

输出格式

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

样例

input

3
1 0
2 0
4 6
0 1
0 2
1 2
1 3
2 3
3 0

output

YES
NO
YES

第一组数据：生产出的零件直接满足条件。 第二组数据：为了产生两个点的零件，必然会发生一次组合操作，而组合操作必然会在两个点之间连边，故不能生产出给定的零件。 第三组数据：对应 $n = 4$ 的第二个图例。

数据范围与提示

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