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.

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.

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