hack:

input:

8 10
1 2
2 3
3 4
1 5
5 6
1 7
4 8
6 1
7 2
8 3

output:

9