B. Dynamic Diameter
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard 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$$$.

Examples
Input
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