H. Graph Isomorphism
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Two undirected graphs with $$$n$$$ vertices $$$G_1$$$ and $$$G_2$$$ are called isomorphic if there is a permutation $$$p_1, p_2, \dots, p_n$$$, such that

$$$$$$ (u, v)\text{ is an edge of }G_1 \iff (p_u, p_v)\text{ is an edge of }G_2 $$$$$$

Given an undirected graph $$$G$$$, you should determine whether it is true that there are no more than $$$n$$$ distinct graphs that are isomorphic to $$$G$$$.

Two undirected graphs with the same number of vertices are considered distinct if their sets of edges are distinct.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). Description of the test cases follows.

The first line of each test case contains two positive integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^5$$$) — the number of vertices and the number of edges in the graph.

Following $$$m$$$ lines contain a pair of integers $$$u$$$ and $$$v$$$ each ($$$1 \leq u, v \leq n$$$), meaning that there is an edge between $$$u$$$ and $$$v$$$.

The graph does not contain loops or multiple edges. It is guaranteed that the sums of $$$n$$$ and $$$m$$$ over all test cases do not exceed $$$10^5$$$ each.

Output

For each test case, output YES if there are at most $$$n$$$ distinct graphs isomorphic to the given graph. Otherwise, output NO.

Example
Input
3
3 3
1 2
2 3
3 1
3 2
1 2
2 3
5 5
1 2
2 3
3 4
4 5
5 1
Output
YES
YES
NO