← 返回题目列表

Codeforces · 1811/F

F. 是花吗?

中文机器翻译题面 查看原题

弗拉德在他的院子里发现了一个有图表的花坛,并决定为自己买一个。后来他发现,那个花坛上除了常见的图形之外,还生长着$$$k$$$-花。如果一个图由一个长度为 $$$k$$$ 的简单循环组成,并且该图的每个顶点都经过其自己的长度为 $$$k$$$ 的简单循环,并且这些循环在顶点处不相交,则该图被称为 $$$k$$$ 花。例如,$$$3$$$-flower 看起来像这样:

请注意,$$$1$$$-flower 和 $$$2$$$-flower 不存在,因为至少需要 $$$3$$$ 顶点才能形成循环。

Vlad 真的很喜欢 $$$k$$$ 花的结构,现在他想知道他是否幸运地从花坛上摘下了其中一朵。

输入

输入的第一行包含单个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中的测试用例数量。

案例描述如下。每个 case 之前都会写入一个空字符串。

每种情况的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le \min(2 \cdot 10^5, \frac{n \cdot (n-1)}{2})$$$) — 图中顶点和边的数量,分别。

接下来的 $$$m$$$ 行包含两个整数,每个 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — 由边连接的顶点数。保证图不包含多边和自环。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。它还保证所有测试用例的总和为$$$m$$$。

输出

输出$$$t$$$行,每一行都是对应测试用例的答案。作为答案,如果 Vlad 的图对于某些 $$$k$$$ 是 $$$k$$$ 花,则输出“YES”,否则输出“NO”。

您可以在任何情况下输出答案(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。

示例

输入 #1

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

输出 #1

YES
NO
NO
NO
NO

输入 #2

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

输出 #2

NO
NO
NO
NO