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("Ofast,fast-math,unroll-loops")
using namespace std;
const int MAXN = 1000 * 1000 + 3;
int n, ans[MAXN], a[MAXN], h[MAXN], siz[MAXN];
vector<int> g[MAXN], vec[MAXN];
bitset<MAXN> ish;
int pfs(int v = 0, int p = -1) {
  int tmx = INT_MIN, sh = -1;
  for (auto u : g[v])
    if (u != p) {
      h[u] = h[v] + 1;
      siz[v] += pfs(u, v);
      if (siz[u] > tmx) {
        tmx = siz[u];
        sh = u;
      }
    }
  if (~sh) ish[sh] = true;
  return ++siz[v];
}
void gfs(int v = 0, int p = -1, bool clr = true) {
  int jav, sh = -1;
  for (auto u : g[v])
    if (u != p && !ish[u])
      gfs(u, v);
    else if (u != p && ish[u])
      sh = u;
  if (~sh)
    gfs(sh, v, false), jav = ans[sh];
  else
    jav = h[v];
  swap(vec[v], vec[sh]);
  for (auto u : g[v])
    if (sh != u && u != p) {
      for (auto i : vec[u]) {
        vec[v].push_back(i);
        a[h[i]]++;
        if (a[h[i]] > a[jav])
          jav = h[i];
        else if (a[h[i]] == a[jav])
          jav = min(jav, h[i]);
      }
      vec[u].clear(), vec[u].shrink_to_fit();
    }
  vec[v].push_back(v);
  a[h[v]]++;
  if (a[h[v]] > a[jav])
    jav = h[v];
  else if (a[h[v]] == a[jav])
    jav = min(jav, h[v]);
  ans[v] = jav;
  if (clr)
    for (auto i : vec[v]) a[h[i]]--;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    g[--x].push_back(--y), g[y].push_back(x);
  }
  pfs(), gfs();
  for (int i = 0; i < n; i++) cout << ans[i] - h[i] << '\n';
  return 0;
}
