12448: One Day Tour In ZJU

Memory Limit:32 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:2 Solved:0

Description

Xiao Ming's parents visit ZJU and Xiao Ming want to take them to look around the campus.They will start from the stone with two famous questions raised by President Zhu Kezhen and end at largest dining room in Asia.They want to visit every place exactly once in ZJU's campus,including the stone and dining room.

Input

The input consists of multiple test cases.
The first line contains an integer n(n<=20),which means the number of place in ZJU's campus.We give numbers(from 1 to n) to the places,especailly,1 means the stone with two famous question and n means the largest dining room.
The second line contains an integer m,which means the number of roads between two place.
Then follows m lines,each line contain two integer,which means there is a road between these two place.The road will not repeat more than one time.

Output

For each test case, you should output one line.If the path exists,you should output 1.Otherwise,you should output 0.

Sample Input Copy

5
4
1 2
1 3
1 4
2 5
6
6
1 3
3 2
1 2
3 4
4 5
5 6

Sample Output Copy

0
1