F. Nanami and Snowflakes
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

No two snowflakes in the world are same.

Nanami sees an object that looks like a snowflake, but she wonders if it is a real snowflake.

She thinks that a real snowflake should consist of a regular polygon inside and a separate identical (isomorphic) "subtree" containing vertices at each vertex of the square polygon. A tree is an undirected acyclic connected graph.

She now gives you an object that looks like a snowflake, and she wants you to decide if it is a real snowflake.

We say that two trees $$$T_1,T_2$$$ are isomorphic if and only if there exists a one-to-one mapping function from a node on $$$T_1$$$ to a node on $$$T_2$$$ while preserving the consistency of the root node.

Input

In the first line, an integer $$$t(1\le t \le 10^4)$$$, representing the number of data sets.

For each group of data:

The first row, two positive integers $$$n,m(3\le n\le 5·10^5;0\le m \le \min(5·10^5,\frac{n-(n-1)}{2}))$$$, represents the number of vertices and edges on the object.

The next consecutive $$$m$$$ rows, each with two positive integers $$$u,v$$$, represent an undirected edge on the object, with the guarantee that the edge will not be given repeatedly and that there is no self-loop in the graph.

There is no guarantee that the given graph is connected.

It is guaranteed that the sum of all $$$n$$$ and $$$m$$$ within the same test point does not exceed $$$5·10^5$$$.

Output

For each set of data, output a line of the string "YES" if the object is a positive snowflake; otherwise, output "NO".

You can output "YES" and "NO" in any case form (e.g., the strings "yES," "yes," and "Yes" will all be treated as positive answers).

Examples
Input
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
Output
YES
NO
YES
NO
NO
Input
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
Output
YES
NO
NO
Note

You can see pictures of Examples in contest materials.