310299: CF1811F. Is It Flower?

F. Is It Flower?time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Vlad found a flowerbed with graphs in his yard and decided to take one for himself. Later he found out that in addition to the usual graphs, $k$-flowers also grew on that flowerbed. A graph is called a $k$-flower if it consists of a simple cycle of length $k$, through each vertex of which passes its own simple cycle of length $k$ and these cycles do not intersect at the vertices. For example, $3$-flower looks like this:

Note that $1$-flower and $2$-flower do not exist, since at least $3$ vertices are needed to form a cycle.

Vlad really liked the structure of the $k$-flowers and now he wants to find out if he was lucky to take one of them from the flowerbed.

Input

The first line of input contains the single integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test.

The descriptions of the cases follow. An empty string is written before each case.

The first line of each case contains two integers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m \le \min(2 \cdot 10^5, \frac{n \cdot (n-1)}{2})$) — the number of vertices and edges in the graph, respectively.

The next $m$ lines contain two integers each $u$ and $v$ ($1 \le u, v \le n$, $u \ne v$) — numbers of vertices connected by an edge. It is guaranteed that the graph does not contain multiple edges and self-loops.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. It is also guaranteed for the sum of $m$ over all test cases.

Output

Output $t$ lines, each of which is the answer to the corresponding test case. As an answer, output "YES" if Vlad's graph is a $k$-flower for some $k$, and "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

ExamplesInput

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

Output

YES
NO
NO
NO
NO

Input

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

Output

NO
NO
NO
NO

题目大意：
弗拉德在他的院子里发现了一个花床，上面长着带有图形的花，他决定为自己拿一朵。后来他发现，除了普通的图形，花床上还长着k-花。如果一个图由一个长度为k的简单循环组成，每个顶点都通过它自己的长度为k的简单循环，并且这些循环在顶点上不交叉，那么这个图就被称为k-花。例如，3-花看起来像这样：

注意，1-花和2-花不存在，因为至少需要3个顶点来形成循环。

弗拉德非常喜欢k-花的结构，现在他想知道他是否有幸从花床上摘下一朵。

输入数据格式：
输入的第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。

接下来是t个测试用例的描述。每个测试用例前写一个空字符串。

每个测试用例的第一行包含两个整数n和m（2≤n≤2×10^5，1≤m≤min(2×10^5, n×(n-1)/2)）——图的顶点数和边数。

接下来的m行每行包含两个整数u和v（1≤u, v≤n，u≠v）——由边连接的顶点数。保证图中不包含多条边和自环。

保证所有测试用例的n之和不超过2×10^5。也保证所有测试用例的m之和不超过2×10^5。

输出数据格式：
输出t行，每行是对应测试用例的答案。如果弗拉德的图是某个k的k-花，则输出“YES”，否则输出“NO”。

你可以以任何大小写输出答案（例如，字符串“yEs”、“yes”、“Yes”和“YES”都将被视为肯定答案）。题目大意： 弗拉德在他的院子里发现了一个花床，上面长着带有图形的花，他决定为自己拿一朵。后来他发现，除了普通的图形，花床上还长着k-花。如果一个图由一个长度为k的简单循环组成，每个顶点都通过它自己的长度为k的简单循环，并且这些循环在顶点上不交叉，那么这个图就被称为k-花。例如，3-花看起来像这样： 注意，1-花和2-花不存在，因为至少需要3个顶点来形成循环。 弗拉德非常喜欢k-花的结构，现在他想知道他是否有幸从花床上摘下一朵。 输入数据格式： 输入的第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 接下来是t个测试用例的描述。每个测试用例前写一个空字符串。 每个测试用例的第一行包含两个整数n和m（2≤n≤2×10^5，1≤m≤min(2×10^5, n×(n-1)/2)）——图的顶点数和边数。 接下来的m行每行包含两个整数u和v（1≤u, v≤n，u≠v）——由边连接的顶点数。保证图中不包含多条边和自环。 保证所有测试用例的n之和不超过2×10^5。也保证所有测试用例的m之和不超过2×10^5。 输出数据格式： 输出t行，每行是对应测试用例的答案。如果弗拉德的图是某个k的k-花，则输出“YES”，否则输出“NO”。 你可以以任何大小写输出答案（例如，字符串“yEs”、“yes”、“Yes”和“YES”都将被视为肯定答案）。