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
n = int(input())
g = {}
p = {}

for _ in range(n-1):
    u, v = map(int, input().split())
    
    if u not in g:
        g[u] = []
    if v not in g:
        g[v] = []
    g[u].append(v)
    g[v].append(u)
    
S    = [1]
p[1] = 0
i    = 0
dp   = {}
d    = {}

while i < len(S):
    u = S[i]
    
    for v in g[u]:
        if v == p[u]: continue
        p[v] = u    
        S.append(v)
    
    i+=1
    
for u in S[::-1]:
    if len(g[u]) == 1 and u != 1:
        dp[u] = [1]
                #depth # nums 
        d[u]  = [0, 1]
    else:
        max_length = -1
        first      = -1
        
        for v in g[u]:
            if v == p[u]: continue
            
            if max_length < len(dp[v]):
                max_length = len(dp[v])
                first  = v
       
        g_point = d[first][0]
        max_    = d[first][1] 
          
        for v in g[u]:
            if v == p[u] or v == first: continue
            
            for i, val in enumerate(dp[v]):
                dp[first][i] += val 
                
                if max_ <= dp[first][i]:
                    max_    = dp[first][i]
                    g_point = i
        
        dp[first].insert(0, 1)
        dp[u] = dp[first]
        
        if max_ == 1:
            d[u]  = [0, 1]
        else:
            d[u]  = [g_point+1, max_] 
        
        for i, val in enumerate(dp[u]):
            if max_ <  val:
                max_    = val
                g_point = i
                
ans = ''      
for k in range(1, n+1):
    ans += str(d[k][0]) + '\n'
print(ans)    