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