Hamiltonian Cycle Detection

Given an undirected graph with n vertices and m edges, determine whether there exists a Hamiltonian cycle in the graph. A Hamiltonian cycle is a cycle that visits every vertex exactly once and returns to the starting vertex. Formally, a sequence of vertices \(v_1, v_2, \dots, v_n\) forms a Hamiltonian cycle if for every \(1 \le i < n\), there exists an edge between \(v_i\) and \(v_{i+1}\) and there is also an edge between \(v_n\) and \(v_1\), i.e., $$ \forall i,\, (v_i,v_{i+1})\in E \quad \text{and} \quad (v_n,v_1)\in E. $$

You are to determine, for each given graph, if such a cycle exists. Note that the graphs considered in this problem are small, so a brute-force approach via permutation checking is acceptable.

inputFormat

The first line of the input contains an integer T indicating the number of test cases. Each test case starts with a line containing two integers n and m, representing the number of vertices and edges, respectively. The following m lines each contain two integers u and v that represent an undirected edge connecting vertex u and vertex v. It is guaranteed that the vertices are numbered from 1 to n.

outputFormat

For each test case, output a single line with either "YES" if a Hamiltonian cycle exists in the graph or "NO" if it does not.

5
4 5
1 2
2 3
3 4
4 1
1 3
3 3
1 2
2 3
3 1
4 3
1 2
2 3
3 4
1 0
4 6
1 2
1 3
1 4
2 3
2 4
3 4

YES
YES
NO
NO
YES