input1
5
1 2
2 3
4 2
3 5

output1
1
4
1
2
1

input2
7
1 2
2 3
3 4
4 5
2 6
3 7

output2
1
5
1
3
1
2
1

@Alex_Wei @tzc_wk @realskc