Hamiltonian Cycle in an Undirected Graph

In this problem, you are given an undirected graph with (N) vertices and (M) edges. Your task is to determine whether the graph contains a Hamiltonian cycle. A Hamiltonian cycle is defined as a cycle that visits each vertex exactly once and returns to the starting vertex. In other words, for a cycle (v_0, v_1, \ldots, v_{N-1}), all vertices are distinct and there is an edge between (v_{N-1}) and (v_0).

For example, given a graph with 3 vertices and edges connecting 0-1, 1-2, and 2-0, the cycle 0 (\to) 1 (\to) 2 (\to) 0 is a Hamiltonian cycle.

inputFormat

The input is read from standard input (stdin). The first line contains two integers (N) and (M), representing the number of vertices and the number of edges in the graph, respectively. The following (M) lines each contain two integers (u) and (v) (0-indexed), representing an undirected edge between vertices (u) and (v).

outputFormat

Print a single integer to standard output (stdout): output 1 if the graph contains a Hamiltonian cycle, or 0 otherwise.## sample

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

1