seuOJ514 - Nanami and Snowflakes

题目描述

情人节，你送给了 Nanami 一朵雪花作为礼物。

Nanami 的到了一个类似雪花的物体，不过她想知道这是不是一片真正的雪花。

她觉得，一片真正的雪花应该是由内部的一个正多边形和在正多边形的每个顶点上的分别的一棵包含顶点的相同（同构）的“子树”组成。一棵树是一个无向无环联通图。

她现在给了你一个像雪花的物体，她想请你判断这是不是真正的雪花。

我们称两颗树T1T_1和T2T_2同构当且仅当保持根节点一致的前提下存在一个从T1T_1上节点到T2T_2上节点上的一一映射函数

输入格式

第一行，一个整数 t(1≤t≤104)t(1\le t \le 10^4)，代表数据组数。

对于每组数据：

第一行，两个正整数 n,m(3≤n≤5⋅105;0≤m≤min⁡(5⋅105,n⋅(n−1)2))n,m(3\le n\le 5·10^5;0\le m \le \min(5·10^5,\frac{n·(n-1)}{2}))，代表物体上的顶点数和边数。

接下来连续的 mm 行，每行两个正整数 u,vu,v，代表物体上的一条无向边，保证边不会重复给出且图中不存在自环。

不保证给出的图是联通的。

保证同一测试点内所有的 nn 和 mm 的总和都不超过 5⋅1055·10^5。

输出格式

对于每组数据，输出一行字符串，如果这个物体是一片正真的雪花，输出 "YES"；否则，输出 "NO"。

你可以输出 "YES "和 "NO" 的任何大小写形式（例如，字符串 "yES"、"yes "和 "Yes" 都将被当作肯定的答案）。

样例

输入样例

5
6 6
1 2
2 3
3 1
1 5
4 2
3 6
4 3
1 2
2 4
3 2
4 4
1 3
3 2
2 4
1 4
9 12
1 2
2 3
3 1
2 4
5 4
2 5
1 7
6 7
1 6
8 3
3 9
8 9
6 6
1 2
2 3
3 1
4 5
6 5
6 4

输出样例

YES
NO
YES
NO
NO

输入样例

3
9 9
1 2
3 2
3 1
3 4
5 3
2 6
1 7
8 2
9 1
12 12
1 2
3 2
3 1
3 4
5 3
2 6
1 7
8 2
9 1
8 6
4 5
7 9
4 3
1 2 
2 3
3 4

输出样例

yes
no
no

你可以在下发的额外材料中看到本题的样例图片。