# Hamiltonian Path

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.

**Input:**

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.

**Output:**

For each test case in a new line print 1 if a Hamiltonean path exists else print 0.

**Constraints:**

1<=T<=100

1<=N<=10

1<=M<=15

**Example:
Input:**

2

4 4

1 2 2 3 3 4 2 4

4 3

1 2 2 3 2 4

**Output:**

1

0

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org