Hamiltonian Cycle
You are given an undirected graph with
n nodes and e edges. Your task is to determine whether the graph contains a Hamiltonian cycle.💡
A Hamiltonian cycle is a path that starts and ends at the same node, visiting each node exactly once.
Input
The first line contains two integers
n (1 ≤ n ≤ 20) and e (0 ≤ e ≤ ), representing the number of nodes and edges in the graph, respectively.The next
e lines represent the edges of the graph. Each line contains two integers a and b (1 ≤ a, b ≤ n, a ≠ b), indicating an edge between nodes a and b.Output
Print
YES if the graph contains a Hamiltonian path or cycle. Otherwise, print NO.Examples
Input | Output |
3 3
1 2
2 3
3 1 | YES |
4 4
1 2
2 3
3 1
2 4 | NO |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB