case 1 failed: answer not optimal: expected 6 got 4
input:
10
1 2
1 3
1 4
2 5
4 6
1 7
3 8
4 9
2 10