Background

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

"Hmm. A vessel must not have the ability to communicate with people, otherwise it may develop thoughts through communication. They should only have the instinct to hunt, and talent for battle. Just like my guards."

"Those are nothing but puppets..."

"A puppet is still better than this guy who can think. Take it away some other day, it is really too noisy... I am tired, I will go for a walk."

The invincible, brave, sexy, mysterious, charming, imposing, diligent, strong, gorgeous, passionate, terrifying, pretty, powerful Gray Prince Zote cursed as he rolled out of the White Palace.

Problem Description

Hallownest has $n$ stag stations and $n$ rails. The $i$-th rail connects stations $u_i$ and $v_i$. Initially, each rail is one-way: the first time you traverse rail $i$, you can only go from $u_i$ to $v_i$. After the first traversal, this rail becomes two-way, so you can travel both from $u_i$ to $v_i$ and from $v_i$ to $u_i$.

Now the White King is at station $1$. He will traverse some rails to reach station $2$, then from station $2$ traverse some rails to reach station $3$... and so on, until station $x$. Since the White King needs to walk through the whole kingdom as soon as possible to investigate the infection, he asks you: for each integer $x$ in $[2,n]$, what is the minimum number of rails that must be traversed?

Input Format

The first line contains an integer $n$, indicating the number of stations and rails.

The next $n$ lines each contain two integers. On the $i$-th line, $u_i, v_i$ means that the first time rail $i$ is traversed, you can only go from $u_i$ to $v_i$, and after that it can be traversed in both directions.

Output Format

Output $n-1$ lines, each containing one number. The $i$-th number indicates the minimum number of rails traversed when $x=i+1$.

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

1
2
3
4
5
10

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

2
4
7
9
11

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

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

Hint

Sample Explanation

For Sample 1, the map is as follows:

For $x=2,3,4,5,6$, the shortest paths all follow $1\to 2\to3\to4\to5\to6$, and the answers are $1,2,3,4,5$.

When $x=7$, if we still follow the path above, we cannot go directly from station $6$ to station $7$ via the rail $7\to 6$, because this rail is still one-way. Detouring back requires traversing $6$ more rails, for a total of $11$ rails.

But if we first traverse $7\to6$ once, i.e. follow the path $1\to7\to6\to7\to1\to2\to3\to4\to5\to6$, then when we arrive at $6$ we can go directly to $7$. In total, only $10$ rails are needed, and it also satisfies visiting nodes $1\sim 7$ in order, making it better than the previous plan.

Constraints

This problem uses bundled testdata.

For $100\%$ of the data, $3\le n\le5\times10^5$.

The testdata guarantees that starting from station $1$, any station is reachable, and there are no multiple edges, self-loops, or 2-cycles.

Translated by ChatGPT 5