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>
#pragma GCC optimize(3)
namespace io {
typedef const int& ci;
const size_t _I_Buffer_Size = 1 << 23, _O_Buffer_Size = 1 << 23;
char _I_Buffer[_I_Buffer_Size], *_I_pos = _I_Buffer - 1;
const char* _I_end = _I_Buffer + _I_Buffer_Size;
char _O_Buffer[_O_Buffer_Size], *_O_pos = _O_Buffer - 1;
const char *_O_end = _O_Buffer + _O_Buffer_Size, *_O_preend = _O_end - 1;
struct io {
  __inline__ __attribute__((always_inline)) ~io() {
    fwrite(_O_Buffer, 1, _O_pos - _O_Buffer + 1, stdout);
  }
} ios;
__inline__ __attribute__((always_inline)) char getchar() {
  return *((++_I_pos == _I_end) ? fread(_I_Buffer, 1, _I_Buffer_Size, stdin),
           _I_pos = _I_Buffer   : _I_pos);
}
__inline__ __attribute__((always_inline)) void putchar(ci x) {
  *((_O_pos == _O_preend) ? fwrite(_O_Buffer, 1, _O_end - _O_Buffer, stdout),
    _O_pos = _O_Buffer    : ++_O_pos) = x;
}
template <typename T1>
__inline__ __attribute__((always_inline)) void readuint(T1& x) {
  int ch;
  while ((ch = getchar() ^ '0') > 9)
    ;
  for (x = ch; (ch = getchar() ^ '0') <= 9; x = x * 10 + ch)
    ;
}
template <typename T1, typename T2>
__inline__ __attribute__((always_inline)) void readuint(T1& x, T2& y) {
  readuint(x);
  readuint(y);
}
template <typename T>
void writeuint(const T& x) {
  if (x > 9) writeuint(x / 10);
  putchar((x % 10) | '0');
}
template <typename T>
__inline__ __attribute__((always_inline)) void writelnuint(const T& x) {
  writeuint(x);
  putchar('\n');
}
}  // namespace io
using namespace std;
using io::readuint;
using io::writelnuint;
typedef const int& ci;
int ans[1000000 + 1];
int hsn[1000000 + 1], dp[1000000 + 1], *top = dp;
struct node {
  int v, nxt;
  __inline__ __attribute__((always_inline)) node() {}
  __inline__ __attribute__((always_inline)) node(ci _v, ci _nxt)
      : v(_v), nxt(_nxt) {}
};
struct graph {
  int head[1000000 + 1], cnt;
  node edge[1000000 << 1 | 1];
  __inline__ __attribute__((always_inline)) void build() {
    memset(head, 0, sizeof(head)), cnt = 0;
  }
  __inline__ __attribute__((always_inline)) void insert(ci u, ci v) {
    push(u, v);
    push(v, u);
  }
  __inline__ __attribute__((always_inline)) void push(ci u, ci v) {
    edge[++cnt] = node(v, head[u]);
    head[u] = cnt;
  }
};
graph g;
int dfs(ci u, ci p) {
  int hsu, hln = 0, sln;
  for (int i = g.head[u], v; i; i = g.edge[i].nxt)
    if ((v = g.edge[i].v) != p)
      if ((sln = dfs(v, u)) > hln) hln = sln, hsu = v;
  if (hln) {
    hsn[u] = hsu;
    return hln + 1;
  }
  hsn[u] = 0;
  return 1;
}
void dfs(ci u) {
  int hsu, hln = 0, sln;
  for (int i = g.head[u], v; i; i = g.edge[i].nxt)
    if ((sln = dfs(v = g.edge[i].v, u)) > hln) hln = sln, hsu = v;
  hsn[u] = hsu;
}
void solve(ci u, ci p);
int solve_ret(ci u, ci p) {
  int* dpu = ++top;
  *dpu = 1;
  int hsu = hsn[u];
  if (hsu) {
    int asu = solve_ret(hsu, u);
    int *dpe = top, num = asu ? dpu[++asu] : 1;
    for (int i = g.head[u], v; i; i = g.edge[i].nxt)
      if ((v = g.edge[i].v) != p && v != hsu) {
        solve(v, u);
        for (int j = top - dpe; j; --j)
          (dpu[j] += dpe[j]) >= num && (num = dpu[j], asu = j);
        top = dpe;
      }
    return ans[u] = asu;
  }
  return 0;
}
void solve(ci u, ci p) {
  int* dpu = ++top;
  *dpu = 1;
  int hsu = hsn[u];
  if (hsu) {
    int asu = solve_ret(hsu, u);
    int *dpe = top, num = asu ? dpu[++asu] : 1;
    for (int i = g.head[u], v; i; i = g.edge[i].nxt)
      if ((v = g.edge[i].v) != p && v != hsu) {
        solve(v, u);
        for (int j = top - dpe; j; --j)
          (dpu[j] += dpe[j]) >= num && (num = dpu[j], asu = j);
        top = dpe;
      }
    ans[u] = asu;
  }
}
int main() {
  int n;
  readuint(n);
  if (n == 1) {
    puts("0");
    return 0;
  }
  g.build();
  for (int i = n, u, v; --i; g.insert(u, v)) readuint(u, v);
  dfs(1);
  memset(ans, 0, sizeof(ans));
  solve(1, 0);
  for (int *i = ans, *ed = ans + n; ++i <= ed; writelnuint(*i))
    ;
  return 0;
}
