test 1 failed
input:
9 2
1 2
2 3
1 4
4 5
2 6
5 7
1 8
8 9
expected:510
got:371