Hamiltonian Cycle Detection

You are given a simple undirected graph with n vertices and m edges. Your task is to determine if the graph contains a Hamiltonian cycle. A Hamiltonian cycle is a cycle that visits each vertex exactly once and returns to the starting vertex. In other words, find whether there exists a permutation \(v_1, v_2, \dots, v_n\) of the vertices such that there is an edge between \(v_i\) and \(v_{i+1}\) for \(1 \leq i < n\) and an edge between \(v_n\) and \(v_1\).

Input/Output: The input begins with an integer T representing the number of test cases. For each test case, the first line contains two integers n and m. The following m lines each contain two integers representing an edge between two vertices. For each test case output "YES" if there is a Hamiltonian cycle, otherwise output "NO".

inputFormat

The first line of the input contains an integer T, the number of test cases. Each test case starts with a line containing two integers n (number of vertices) and m (number of edges). Then follow m lines, each with two integers u and v indicating that there is an undirected edge between vertices u and v.

outputFormat

For each test case, output a single line containing either "YES" if the graph contains a Hamiltonian cycle, or "NO" otherwise.

3
3 3
1 2
2 3
3 1
4 4
1 2
2 3
3 4
4 1
4 3
1 2
2 3
3 4

YES
YES
NO