test 3 failed:
input:
18
1 2
2 3
3 4
4 5
2 6
2 7
7 8
4 9
9 10
5 11
7 12
3 13
6 14
2 15
1 16
2 17
16 18
expected 9 got 12