A Hamiltonian path, is a path in an undirected or directed graph that visits each vertex exactly once. Given an undirected graph the task is to check if a Hamiltonian path is present in it or not.
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains two lines. The first line consists of two space separated integers N and M denoting the number of vertices and number of edges.Then in the next line are M space separated pairs u,v denoting an edge from u to v.
For each test case in a new line print 1 if a Hamiltonean path exists else print 0.
1 2 2 3 3 4 2 4
1 2 2 3 2 4
Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org