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