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 sys import stdin
input=lambda :stdin.readline()[:-1]

n=int(input())
edge=[[] for i in range(n)]
for _ in range(n-1):
  x,y=map(lambda x:int(x)-1,input().split())
  edge[x].append(y)
  edge[y].append(x)

dp=[[] for i in range(n)]
ans=[(0,1)]*n
todo=[(0,0,-1)]
while todo:
  t,v,p=todo.pop()
  if t==0:
    for u in edge[v]:
      if u!=p:
        todo.append((1,u,v))
        todo.append((0,u,v))
  else:
    dp[v].append(1)
    print(v,dp[v])
    if len(dp[v])<=len(dp[p]):
      pass
    else:
      if ans[p][1]<ans[v][1]:
        ans[p]=(ans[v][0]+1,ans[v][1])
      elif ans[p][1]==ans[v][1]:
        ans[p]=(min(ans[v][0]+1,ans[p][0]),ans[v][1])
      dp[p],dp[v]=dp[v],dp[p]
    for i in range(len(dp[v])):
      dp[p][-i-1]+=dp[v][-i-1]
      if ans[p][1]<dp[p][-i-1]:
        ans[p]=(i+1,dp[p][-i-1])
      elif ans[p][1]==dp[p][-i-1] and ans[p][0]>i+1:
        ans[p]=(i+1,dp[p][-i-1])
    #print(dp[v],dp[p])

for i in ans:
  print(i[0])