Traverse the Enchanted Tracks

In Saint’s Nest there are ( n ) deer-antler stations and ( n ) tracks. The ( i)th track connects stations ( u_i ) and ( v_i ). Initially, each track is one‐way: the very first time you traverse track ( i ) you can only go from ( u_i ) to ( v_i ). Right after the first traversal the track becomes bidirectional, i.e. you can then travel between ( u_i ) and ( v_i ) in either direction.


Now, the White King starts at station 1 and wants to visit a sequence of stations. He must travel from station 1 to station 2, then from station 2 to station 3, and so on, until he reaches station ( x ) (with ( x ) taking every integer value from 2 to ( n )). For each ( x ) you are to determine the minimum number of tracks that must be used in order to accomplish the journey.

Note: When an edge is traversed for the first time, it must be used in its allowed direction (i.e. from ( u_i ) to ( v_i )). Once used, the track becomes bidirectional and may be used in either direction in subsequent traversals.

inputFormat

The first line contains a single integer ( n ) denoting the number of stations (and also the number of tracks).

Then ( n ) lines follow; the ( i)th of these contains two integers ( u_i ) and ( v_i ), indicating that the ( i)th track connects station ( u_i ) and station ( v_i ), and its initial allowed direction is from ( u_i ) to ( v_i ).

outputFormat

Output ( n-1 ) integers. The ( k)th integer (for ( k=1,2,\ldots,n-1 )) should be the minimum number of tracks needed to travel from station 1 to station ( k+1 ) while visiting stations 1, 2, ( \ldots, k+1 ) in order. If it is impossible to reach station ( k+1 ) under these conditions, output -1 for that case.

sample

3
1 2
2 3
3 1

1 2