Maybe these tests will help you:

4 4
1 2
3 4
2 1
1 2
ans: No

8 9
1 2
1 3
1 4
5 6
7 2
7 3
7 4
8 9
ans: No

14 14
1 2
5 4
4 3
2 3
2 6
6 7
13 8
12 11
11 10
10 9
9 8
7 8
7 14
14 6
Answer: Yes 1 5 4 3 2 6 13 12 11 10 9 8 7 14