Problem Statement

You are given a tree with $N$ vertices.
Each vertex is assigned a distinct number from $1$ to $N$, and vertex $1$ is the root of this tree.
For a vertex $i$, let $R_i$ be its distance from the root, and $L_i$ be its distance from the nearest leaf.
Output $min(R_i, L_i)$ in order of vertex number.

Note: The minimum number of edges traversed when moving from vertex $u$ to vertex $v$ is defined as the distance from vertex $u$ to vertex $v$ (the distance from vertex $v$ to vertex $u$).

Input

$N$
$x_1$ $y_1$
$\vdots$
$x_{N-1}$ $y_{N-1}$

The first line contains the number of vertices $N$.
The following $N-1$ lines contain the edge information, separated by spaces. The $i$-th edge connects vertices $x_i$ and $y_i$.
All inputs are integers and satisfy the following constraints.
$ 2 \leq N \leq 10^5$
$ 1 \leq x_i < y_i \leq N$
It is guaranteed that $ x_i \neq x_j $ or $ y_i \neq y_j $ when $ i \neq j $. That is, there are no multiple edges or self-loops, and the tree is connected.

Output

$min(R_1, L_1)$
$\vdots$
$min(R_N, L_N)$

Output $min(R_i, L_i)$ on the $i$-th line.

Sample

6
1 2
1 3
2 4
2 5
5 6

0
1
0
0
1
0

6
1 2
2 3
3 4
4 5
5 6

0
1
2
2
1
0