case 1 failed
input:
1
6
1 2
2 3
2 4
4 5
2 6
expected: 4
got: 5