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;
constexpr int seed = 131;
constexpr long long LLMAX = 2e18;
constexpr int MOD = 1e9 + 7;
constexpr double eps = 1e-8;
constexpr int MAXN = 1e6 + 10;
constexpr int hmod1 = 0x48E2DCE7;
constexpr int hmod2 = 0x60000005;
inline long long sqr(long long x) { return x * x; }
inline int sqr(int x) { return x * x; }
inline double sqr(double x) { return x * x; }
inline int mul(int x, int y) { return 1ll * x * y % MOD; }
inline int sub(int x, int y) { return x >= y ? x - y : MOD + x - y; }
inline int add(int x, int y) { return x + y >= MOD ? x + y - MOD : x + y; }
inline int dcmp(double x) {
  if (fabs(x) < eps) return 0;
  return (x > 0 ? 1 : -1);
}
inline long long qpow(long long a, long long n) {
  long long sum = 1;
  while (n) {
    if (n & 1) sum = sum * a % MOD;
    a = a * a % MOD;
    n >>= 1;
  }
  return sum;
}
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long exgcd(long long a, long long b, long long &x, long long &y) {
  long long d;
  (b == 0 ? (x = 1, y = 0, d = a)
          : (d = exgcd(b, a % b, y, x), y -= a / b * x));
  return d;
}
vector<int> G[MAXN];
int d[MAXN], son[MAXN], dfn[MAXN], top[MAXN], cnt, far[MAXN], dp[MAXN],
    *p[MAXN], ans[MAXN];
void dfs1(int u, int fa) {
  d[u] = 1;
  far[u] = fa;
  for (int i = 0; i < (int)G[u].size(); i++) {
    int v = G[u][i];
    if (v != fa) {
      dfs1(v, u);
      d[u] = max(d[u], d[v] + 1);
      if (d[v] > d[son[u]]) son[u] = v;
    }
  }
}
void dfs2(int u, int fa) {
  top[u] = fa;
  dfn[u] = ++cnt;
  p[u] = dp + cnt;
  if (son[u]) dfs2(son[u], fa);
  for (int i = 0; i < (int)G[u].size(); i++) {
    int v = G[u][i];
    if (v != far[u] && v != son[u]) dfs2(v, v);
  }
}
void solve(int u) {
  if (son[u]) {
    solve(son[u]);
    ans[u] = ans[son[u]] + 1;
  }
  p[u][0] = 1;
  if (p[u][ans[u]] <= 1) ans[u] = 0;
  for (int i = 0; i < (int)G[u].size(); i++) {
    int v = G[u][i];
    if (v != far[u] && v != son[u]) {
      solve(v);
      for (int j = 0; j < d[v]; j++) {
        p[u][j + 1] += p[v][j];
        if (p[u][j + 1] > p[u][ans[u]])
          ans[u] = j + 1;
        else if (p[u][j + 1] == p[u][ans[u]] && j + 1 < ans[u])
          ans[u] = j + 1;
      }
    }
  }
}
int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    G[u].push_back(v), G[v].push_back(u);
  }
  dfs1(1, 0);
  dfs2(1, 1);
  solve(1);
  for (int i = 1; i <= n; i++) cout << ans[i] << endl;
  return 0;
}
