You are given a rooted undirected tree consisting of $n$ vertices. Vertex $1$ is the root.

Let's denote a depth array of vertex $x$ as an infinite sequence $[d_{x, 0}, d_{x, 1}, d_{x, 2}, \dots]$, where $d_{x, i}$ is the number of vertices $y$ such that both conditions hold:
 -  $x$ is an ancestor of $y$; -  the simple path from $x$ to $y$ traverses exactly $i$ edges. 
The dominant index of a depth array of vertex $x$ (or, shortly, the dominant index of vertex $x$) is an index $j$ such that:
 -  for every $k &lt; j$, $d_{x, k} &lt; d_{x, j}$; -  for every $k &gt; j$, $d_{x, k} \le d_{x, j}$. 
For every vertex in the tree calculate its dominant index.
The first line contains one integer $n$ ($1 \le n \le 10^6$) — the number of vertices in a tree.

Then $n - 1$ lines follow, each containing two integers $x$ and $y$ ($1 \le x, y \le n$, $x \ne y$). This line denotes an edge of the tree.

It is guaranteed that these edges form a tree.
4
1 2
2 3
3 4
0
0
0
0
4
1 2
1 3
1 4
1
0
0
0
4
1 2
2 3
2 4
2
1
0
0
1
0
2
1 2
0
0
from collections import deque
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def bfs(s):
    q = deque()
    q.append(s)
    visit = [0] * (n + 1)
    visit[s] = 1
    child = [[] for _ in range(n + 1)]
    p = []
    while q:
        i = q.popleft()
        p.append(i)
        for j in G[i]:
            if not visit[j]:
                q.append(j)
                visit[j] = 1
                child[i].append(j)
    return child, p

n = int(input())
G = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    G[u].append(v)
    G[v].append(u)
child, p = bfs(1)
d = [[] for _ in range(n + 1)]
ans = [0] * n
while p:
    i = p.pop()
    if not len(child[i]):
        d[i].append(1)
        continue
    ma, k = 0, 0
    for j in child[i]:
        if ma < len(d[j]):
            ma, k = len(d[j]), j
    ans0 = ans[k - 1] + 1
    dk = d[k]
    ma = dk[-ans0]
    for j in child[i]:
        if not j ^ k:
            continue
        dj = d[j]
        for l in range(len(dj)):
            dk[l] += dj[l]
            if ma <= dk[l]:
                ma = dk[l]
                ans0 = len(dk) - l
    d[i], d[k] = d[k], d[i]
    d[i].append(1)
    if not ma ^ 1:
        ans0 = 0
    ans[i - 1] = ans0
sys.stdout.write("\n".join(map(str, ans)))