407025: GYM102694 B Dynamic Diameter

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).

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$$$

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$$$.

1

1

3
3 2
2 1

3
2
3

5
4 2
1 4
5 4
3 4

3
3
3
2
3