407025: GYM102694 B Dynamic Diameter

Memory Limit:256 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Dynamic Diametertime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given $$$n+1$$$ nodes and $$$n-1$$$ edges where the first $$$n$$$ nodes are a tree and node $$$n+1$$$ is in its own component. For each node $$$i$$$ from $$$1 ... n$$$, answer the following question:

If an edge was added from node $$$i$$$ to node $$$n+1$$$, what would the diameter of the created tree be? (Notice that the $$$n+1$$$ nodes will be a tree if this edge was added).

Input

The first line will contain a single integer $$$n$$$, the number of nodes in the tree initial tree. $$$n-1$$$ lines follow, each containing two different integers, describing the edges initially in the tree. Additional constraint on input: these edges will form a tree on the first $$$n$$$ nodes.

$$$1 \leq n \leq 3*10^5$$$

Output

Print $$$n$$$ integers, each on their own line. The $$$i$$$th is the diameter of the new tree if you were to add an edge from node $$$i$$$ to node $$$n+1$$$.

ExamplesInput
1
Output
1
Input
3
3 2
2 1
Output
3
2
3
Input
5
4 2
1 4
5 4
3 4
Output
3
3
3
2
3

加入题单

上一题 下一题 算法标签: