Problem Background

"My king, this child... is not pure... he..."

"Hmm. The container should not possess the ability to communicate with humans, as it might develop thoughts during communication. It should only have the instinct to hunt and the talent for battle, just like my guards."

"Those are merely puppets..."

"Puppets are better than this thinking creature. Take it away someday, it's really noisy... I'm tired, I'm going for a walk."

The invincible, brave, sexy, mysterious, charming, divine, diligent, strong,华丽, passionate, terrifying, beautiful, powerful Gray Prince Zuo Te grumbled and rolled out of the White Palace.

Problem Description

The Holy Nest has $n$ stag beetle stations and $n$ tracks. The $i$-th track connects two stations $u_i$ and $v_i$. Initially, the tracks are unidirectional. The first time you pass the $i$-th track, you can only go from $u_i$ to $v_i$; after the first pass, the track becomes bidirectional, allowing travel from $u_i$ to $v_i$ and from $v_i$ to $u_i$.

Now, the White King is at station 1. He needs to pass through several tracks to reach station 2, then from station 2 through several tracks to reach station 3, and so on, up to station $x$. Since the White King needs to quickly traverse the entire kingdom to investigate the plague situation, he asks you for the minimum number of tracks required for each integer $x$ in the range $[2, n]$.

Input Format

The first line contains an integer $n$, representing the number of stations and tracks.

The next $n$ lines each contain two integers. The $i$-th line contains $u_i$ and $v_i$, indicating that the first time you pass the $i$-th track, you can only go from $u_i$ to $v_i$, after which it becomes bidirectional.

Output Format

Output $n-1$ lines, each containing a number. The $i$-th number represents the minimum number of tracks required when $x = i+1$.

Sample Input and Output

Sample Input #1

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

Sample Output #1

1
2
3
4
5
10

Sample Input #2

6
1 4
4 2
2 6
6 1
6 3
1 5

Sample Output #2

2
4
7
9
11

Sample Input #3

18
14 15
8 12
5 4
10 14
15 17
7 5
3 9
9 18
11 13
1 2
16 10
5 11
5 6
6 8
2 3
2 7
18 16
7 10

Sample Output #3

1
2
6
7
8
10
13
19
22
26
30
35
40
41
45
49
54

Notes

Sample Explanation

For Sample 1, the map is as follows:

The shortest paths for $x=2,3,4,5,6$ are all along the path $1\to 2\to 3\to 4\to 5\to 6$, with answers being $1,2,3,4,5$.

For $x=7$, if you still follow the above path, you cannot directly pass through the track $7\to 6$ from station 6 to station 7 because the track is still unidirectional. Taking a detour back requires passing through 6 more tracks, totaling 11 tracks.

However, if you first pass through $7\to 6$, i.e., along the path $1\to 7\to 6\to 7\to 1\to 2\to 3\to 4\to 5\to 6$, when you arrive at station 6, you can directly go to station 7, totaling only 10 tracks, which is also in line with the requirement to pass through stations 1 to 7 sequentially, and is a better solution than the previous one.

Data Range

This problem uses subtask testing.

For $100\%$ of the data, $3 \le n \le 5\times 10^5$.

The data guarantees that you can reach any station from station 1, and there are no duplicate edges, self-loops, or binary loops.

见题面 Input 部分

见题面 Output 部分