Migrated from Lutece 2987 虚数空间

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

“现在，你置身于一个存在于现实但又完全隔离的空间之中。”

“你看着身边一团团亮光，不断在这个漆黑的空间中旋转运动着。”

“有的光团相撞，发出一刹那耀眼光芒然后消失；有的光团为了避免湮灭，用巨大的外壳将自己包裹起来，换上虚假的天空。”

“你仔细望去，发现那一个个光团，正是一个个小小的宇宙。”

“这些宇宙之间是不同的吗？还是说这些是同一时间下的平行宇宙？你在时间之外无尽的思考着。”

“此时，封闭的世界因外来的双子而发生着微妙的变换，开始发出淡淡光辉；同时，一辆小小的列车，划过一个个光团的星空不断跳跃着。”

“你用手向着列车挥去，但就像挥过的虚影，没有触及任何实体；但你所不知道的是，一位星神惊恐的望着你的手，逃离而去，最终化为一个光点。”

“光团不断湮灭着，又不断产生；你知道着一切同时又对一切充满了无知。”

“此时，你将所有的光团用你手中名为 ‘命运’ 的双向织线连结起来，并好奇的想知道，在无尽的随机组合中，是否存在有相同命运的两个时空。”

“你打开手边不知道从哪来的系统，上面信息如下：”

”查看信息总览。“

目前该虚数空间可客观且不干扰的观测到 $n$ 个实数质团（也就是你看到的所谓的光团），有 $m$ 条事件引导线（你所谓的 ‘命运’ 织线）将它们连结。一个时间线下的世界（一个时空）仅包含 $n-1$ 条事件引导线将这 $n$ 个实数质团连结。

”如何判断两个时空相同。“

搜索中...

结果：两个时空 $A$ 和 $B$ 相同的条件为，当且仅当在这两个时空的实数质团之间存在一个双射（$f:V(A) \rightarrow V(B)$），使得在时空 $A$ 中事件引导线相连的两个质团 $u,v$，映射在时空 $B$ 中的$f(u),f(v)$ 也是相连的。

”由于数出所有可能的不同命运时空太难，所以你只想知道是否存在一个时空模板，使得你所观测到的这个空间内所有可能的时空均和其相同。“

简化题意： 给你一个 $n$ 个点，$m$ 条无向边的连通图（无重边无自环），问你是否存在一个树，使得该图的所有含 $n$ 个节点，$n-1$ 条边的生成子图与该树同构。两个图$A,B$同构当且仅当存在一个节点的双射$f:V(A) \rightarrow V(B)$，使得 $A$ 图中相邻的点 $u,v$ ,在 $B$ 图里面对应的 $f(u),f(v)$ 节点也是相邻的。

Input

第一行一个数字 $T$，表示你观测的次数。

对于每一次观测，输入信息格式如下：

第一行两个数字 $n,m$ 表示有 $n$ 个光团和 $m$ 条命运织线。

接下来 $m$ 行每行两个数字 $u_i,v_i (u_i\not =v_i)$ 表示你将一条命运织线连接在了 $u_i$ 号光团和 $v_i$ 号光团之间。

你不会重复的连接两个光团，且你最后一定会将整个观测的所有光团连接起来。

Output

对于每一次观测，输出YES表示你所想要的时空模板存在，反之输出NO。

Samples

4
3 3
1 2
2 3
3 1
5 5
1 2
2 3
3 4
4 1
1 5
1 0
7 6
1 2
2 3
3 4
4 5
5 6
3 7

YES
NO
YES
YES

Constraints

$$1\leq T\leq 10^5 \\ 1\leq n\leq 10^5, n-1\leq m\leq 10^5 \\ 1\leq u_i,v_i\leq n \\ 1\leq \sum n,\sum m\leq10^6 $$

Note

题面仅供娱乐（雾

Resources

2023 UESTC ICPC Training for Graph