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>
using namespace std;
inline int rd() {
  int x = 0;
  char c = getchar();
  while (!isdigit(c)) {
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }
  return x;
}
inline int max(const int &x, const int &y) { return x < y ? y : x; }
inline int min(const int &x, const int &y) { return x > y ? y : x; }
struct Node {
  int l, r, tot, id;
} t[1000006 << 1];
struct Edge {
  int to, nx;
} e[1000006 << 1];
int n, x, y, mxd, cnt, tot;
int siz[1000006], dep[1000006], rub[1000006], ans[1000006], tmp[1000006],
    h[1000006], rt[1000006];
inline void add(int u, int v) {
  e[++cnt].to = v;
  e[cnt].nx = h[u];
  h[u] = cnt;
}
void dfs1(int u, int pre) {
  dep[u] = dep[pre] + 1;
  siz[u] = 1;
  mxd = mxd < dep[u] ? dep[u] : mxd;
  for (int i = h[u]; i; i = e[i].nx) {
    int v = e[i].to;
    if (v != pre) {
      dfs1(v, u);
      siz[u] += siz[v];
    }
  }
}
inline int New() {
  if (*rub) {
    return rub[(*rub)--];
  }
  return ++tot;
}
inline void Del(int p) {
  t[p].l = t[p].r = t[p].tot = t[p].id = 0;
  rub[++*rub] = p;
}
inline void pushup(int p) {
  t[p].tot = max(t[t[p].l].tot, t[t[p].r].tot);
  t[p].id = t[t[p].l].tot >= t[t[p].r].tot ? t[t[p].l].id : t[t[p].r].id;
}
void update(int &p, int x, int l = 1, int r = mxd) {
  if (!p) {
    p = New();
  }
  if (l == r) {
    ++t[p].tot;
    t[p].id = l;
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid) {
    update(t[p].l, x, l, mid);
  } else {
    update(t[p].r, x, mid + 1, r);
  }
  pushup(p);
}
int merge(int a, int b, int l = 1, int r = mxd) {
  if (!a || !b) {
    return a | b;
  }
  if (l == r) {
    t[a].tot += t[b].tot;
    Del(b);
    return a;
  }
  int mid = (l + r) >> 1;
  t[a].l = merge(t[a].l, t[b].l, l, mid);
  t[a].r = merge(t[a].r, t[b].r, mid + 1, r);
  Del(b);
  pushup(a);
  return a;
}
bool cmp(const int &x, const int &y) { return siz[x] > siz[y]; }
void dfs2(int u, int pre) {
  int l = *tmp + 1;
  for (int i = h[u]; i; i = e[i].nx) {
    if (e[i].to != pre) {
      tmp[++*tmp] = e[i].to;
    }
  }
  int r = *tmp;
  sort(tmp + l, tmp + 1 + r, cmp);
  for (int i = l; i <= r; ++i) {
    dfs2(tmp[i], u);
    rt[u] = merge(rt[u], rt[tmp[i]]);
  }
  update(rt[u], dep[u]);
  ans[u] = t[rt[u]].id - dep[u];
}
int main() {
  n = rd();
  for (int i = 1; i < n; ++i) {
    x = rd(), y = rd();
    add(x, y), add(y, x);
  }
  dfs1(1, 0), dfs2(1, 0);
  for (int i = 1; i <= n; ++i) {
    printf("%d\n", ans[i]);
  }
  return 0;
}
