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.
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.
For each test case, output YES if there are at most $$$n$$$ distinct graphs isomorphic to the given graph. Otherwise, output NO.
33 31 22 33 13 21 22 35 51 22 33 44 55 1
YES YES NO
Name |
---|