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}, \dots]$, 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 &lt; j$, $d_{x, k} &lt; d_{x, j}$; -  for every $k &gt; j$, $d_{x, k} \le d_{x, j}$. 
For every vertex in the tree calculate its dominant index.
The first line contains one integer $n$ ($1 \le n \le 10^6$) — the number of vertices in a tree.

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

It is guaranteed that these edges form a tree.
4
1 2
2 3
3 4
0
0
0
0
4
1 2
1 3
1 4
1
0
0
0
4
1 2
2 3
2 4
2
1
0
0
1
0
2
1 2
0
0
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include "bits/stdc++.h"
#include <random>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

const ll mod = 1e9 + 7;
const ll inf = 1e9;
const int maxn = 1e6;

vector<int> g[maxn];
vector<int> h[maxn];
int ans[maxn];
int mx[maxn];

void dfs(int v, int p = -1) {
    for (auto& u : g[v]) {
        if (u == p) continue;
        dfs(u, v);
        if (h[u].size() > h[v].size()) swap(h[v], h[u]);
        if (mx[u] > mx[v]) {
            ans[v] = ans[u] + 1;
            mx[v] = mx[u];
        }
    }



    for (auto& u : g[v]) {
        if (u == p) continue;
        int x = (int)h[v].size() - 1;
        for (int i = 0; i < h[u].size(); i++) {
            h[v][x - i] += h[u][(int)h[u].size() - 1 - i];
            if (h[v][x - i] > mx[v]) {
                mx[v] = h[v][x - i];
                ans[v] = i + 1;
            }
        }
        h[u].clear();
    }
    h[v].push_back(1);
}

void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int v, u;
        cin >> v >> u;
        v--, u--;
        g[v].push_back(u);
        g[u].push_back(v);
    }

    dfs(0);

    for (int i = 0; i < n; i++) {
        cout << ans[i] << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    //cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}
