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}, ...], 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 < j, d_{x, k} < d_{x, j}; 
  * for every k > j, d_{x, k} ≤ d_{x, j}. 



For every vertex in the tree calculate its dominant index.

Input

The first line contains one integer n (1 ≤ n ≤ 10^6) — the number of vertices in a tree.

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

It is guaranteed that these edges form a tree.

Output

Output n numbers. i-th number should be equal to the dominant index of vertex i.

Examples

Input

4
1 2
2 3
3 4


Output

0
0
0
0


Input

4
1 2
1 3
1 4


Output

1
0
0
0


Input

4
1 2
2 3
2 4


Output

2
1
0
0
#include <bits/stdc++.h>
bool isp(int x) {
  if (x < 2) return 0;
  for (int i = 2; i <= sqrt(x); i++) {
    if (x % i == 0) return 0;
  }
  return 1;
}
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - 48;
    ch = getchar();
  }
  return x * f;
}
int gcd(int x, int y) { return !y ? x : gcd(y, x % y); }
using namespace std;
int ans[2000005], N, cnt;
int R;
int dp[2000005], id[2000005];
int dep[2000005], sz[2000005], son[2000005], fa[2000005], top[2000005], tot,
    h[2000005], idx[2000005];
struct eds {
  int u, v, n;
} edge[2000005];
void add(int x, int y) {
  edge[++tot].u = x;
  edge[tot].v = y;
  edge[tot].n = h[x];
  h[x] = tot;
}
void dfs1(int now, int f, int depth) {
  dep[now] = depth;
  fa[now] = f;
  int maxson = -1;
  for (int i = h[now]; i != -1; i = edge[i].n) {
    if (edge[i].v == f) continue;
    dfs1(edge[i].v, now, depth + 1);
    sz[now] = max(sz[now], sz[edge[i].v]);
    if (sz[edge[i].v] > maxson) maxson = sz[edge[i].v], son[now] = edge[i].v;
  }
  sz[now]++;
  return;
}
int tt = 0, pre[2000005];
void dfs2(int now, int topf) {
  idx[now] = ++cnt;
  top[now] = topf;
  if (!son[now]) return;
  dfs2(son[now], topf);
  for (int i = h[now]; i != -1; i = edge[i].n) {
    int to = edge[i].v;
    if (to != fa[now] && to != son[now]) {
      dfs2(to, to);
    }
  }
}
int loc(int x, int y) { return idx[x] + y; }
void solve(int now) {
  dp[idx[now]] = 1;
  if (son[now]) {
    solve(son[now]);
    if (dp[loc(now, ans[son[now]] + 1)] > dp[loc(now, ans[now])] ||
        (dp[loc(now, ans[son[now]] + 1)] == dp[loc(now, ans[now])] &&
         ans[now] > ans[son[now]] + 1))
      ans[now] = ans[son[now]] + 1;
  }
  for (int i = h[now]; i != -1; i = edge[i].n) {
    if (edge[i].v != fa[now] && edge[i].v != son[now]) {
      solve(edge[i].v);
      for (int j = 0; j < sz[edge[i].v]; j++)
        dp[loc(now, j + 1)] += dp[loc(edge[i].v, j)];
      for (int j = 0; j <= sz[edge[i].v] + 1; j++)
        if (dp[loc(now, j)] > dp[loc(now, ans[now])] ||
            (dp[loc(now, j)] == dp[loc(now, ans[now])] && ans[now] > j))
          ans[now] = j;
    }
  }
}
int main() {
  cin >> N;
  memset(h, -1, sizeof(h));
  int u, v;
  for (int i = 1; i < N; i++) {
    cin >> u >> v;
    add(u, v);
    add(v, u);
  }
  dfs1(1, 0, 1);
  dfs2(1, 1);
  solve(1);
  for (int i = 1; i <= N; i++) printf("%d\n", ans[i]);
  return 0;
}
