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