I wrote a program about this problem but wa4....
I found an AC code but it can not pass this data,and I can pass.
8 12
1 2
2 3
3 4
4 1
1 5
2 6
3 7
4 8
5 6
6 7
7 8
8 5

here is my answer:
4
5 6 7 8 5 1 2 3 4 1
6 2
7 3
8 4

here is ac code answer:
7
1 2 3 1 4 3
4 5 1 6 5
6 7 1 8 7
8 9 1 10 9
10 11 1 12 11
12 13 1 14 13
14 2
I think he is wrong.

Please add this kind of data.
And I wanted to know the test for test 4.
Could you please tell me?
At last,sorry for my poor English.

I got an AC,if you wa4,you can try this test
20 25
5 14
11 17
19 7
1 12
3 1
10 8
2 6
17 4
11 10
2 4
6 9
3 16
7 11
20 4
6 10
9 12
16 9
9 15
17 5
11 13
15 6
13 9
17 9
19 8
18 17

Your test was added

the right answer is three , why the answer which you tell me is five ?
you played a trick on ME !!
3
10 6 15 9 17
14 5 17 18
20 4 2 6 9 16 3 1 12 9 13 11 7 19 8 10 11 17 4