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
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.List;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Pradyumn
 */
public class Main {
    public static void main(String[] args) throws InterruptedException {
        Thread t = new Thread(null, null, ":)", Runtime.getRuntime().maxMemory()) {
            @Override
            public void run() {
                InputStream inputStream = System.in;
                OutputStream outputStream = System.out;
                FastReader in = new FastReader(inputStream);
                PrintWriter out = new PrintWriter(outputStream);
                TaskF solver = new TaskF();
                solver.solve(1, in, out);
                out.close();
            }
        };
        t.start();
        t.join();
    }

    static class TaskF {
        static List<Integer>[] g;
        static int[] ans;
        static int[] count;
        static int[] discover;
        static int[] begin;
        static int[] end;
        static int[] level;
        static int[] size;
        static int[] parent;

        private static void dfs(int cur, int par, boolean keep) {
            int bigChild = -1;
            for (Integer next : g[cur]) {
                if (next == par) continue;
                if (bigChild == -1 || size[bigChild] < size[next])
                    bigChild = next;
            }
            for (Integer next : g[cur])
                if (next != par && next != bigChild)
                    dfs(next, cur, false);
            ans[cur] = level[cur];
            size[cur] = 1;
            if (bigChild != -1) {
                dfs(bigChild, cur, true);
                if (size[bigChild] > size[cur]) {
                    ans[cur] = ans[bigChild];
                    size[cur] = size[bigChild];
                }
            }

            count[level[cur]] = 1;
            for (Integer next : g[cur]) {
                if (next != par && next != bigChild) {
                    for (int p = begin[next]; p <= end[next]; ++p) {
                        ++count[level[discover[p]]];

                        if (count[level[discover[p]]] > size[cur]) {
                            size[cur] = count[level[discover[p]]];
                            ans[cur] = level[discover[p]];
                        } else if (count[level[discover[p]]] == size[cur]) {
                            ans[cur] = Math.min(ans[cur], level[discover[p]]);
                        }
                    }
                }
            }


            if (!keep) {
                for (int p = begin[cur]; p <= end[cur]; ++p)
                    --count[level[discover[p]]];
            }
        }

        public void solve(int testNumber, FastReader in, PrintWriter out) {
            Debug debug = new Debug(out);
            int n = in.nextInt();
            g = GraphUtils.nextU(in, n, n - 1, true);
            count = new int[n];
            ans = new int[n];
            EulerTour eulerTour = new EulerTour(g);
            discover = eulerTour.discover;
            begin = eulerTour.begin;
            end = eulerTour.end;
            level = eulerTour.level;
            parent = eulerTour.parent;
            size = new int[n];
            ArrayUtils.fill(size, 1);
            int[] ord = GraphUtils.parents3(g, 0)[1];
            for (int i = n - 1; i >= 1; --i) size[parent[ord[i]]] += size[ord[i]];
            dfs(0, -1, true);
            for (int i = 0; i < n; ++i) out.println(ans[i] - level[i]);
        }

    }

    static class ArrayUtils {
        public static void fill(int[] array, int value) {
            Arrays.fill(array, value);
        }

    }

    static class EulerTour {
        public int[] discover;
        public int[] begin;
        public int[] end;
        public int[] level;
        public int[] parent;
        public int[] indexes;

        public EulerTour(List<Integer>[] g) {
            int n = g.length;
            int[] stack = new int[n];
            int pos = 0;
            discover = new int[n];
            begin = new int[n];
            end = new int[n];
            level = new int[n];
            parent = new int[n];
            indexes = new int[n];
            boolean[] visited = new boolean[n];
            stack[pos++] = 0;
            level[0] = 0;
            parent[0] = -1;
            int clock = 0;
            int count = 0;
            outer:
            while (pos != 0) {
                int cur = stack[pos - 1];
                if (!visited[cur]) {
                    begin[cur] = clock++;
                    discover[count++] = cur;
                    visited[cur] = true;
                }
                while (indexes[cur] < g[cur].size()) {
                    int next = g[cur].get(indexes[cur]++);
                    if (parent[cur] != next) {
                        parent[next] = cur;
                        level[next] = level[cur] + 1;
                        stack[pos++] = next;
                        continue outer;
                    }
                }
                pos--;
                if (indexes[cur] == g[cur].size()) end[cur] = clock - 1;
            }
        }

    }

    static class GraphUtils {
        public static List<Integer>[] nextU(FastReader in, int n, int m, boolean oneIndexed) {
            int diff = oneIndexed ? 1 : 0;
            List<Integer>[] g = new List[n];
            for (int i = 0; i < n; ++i) g[i] = new ArrayList<>();
            for (int i = 0; i < m; ++i) {
                int u = in.nextInt() - diff;
                int v = in.nextInt() - diff;
                g[u].add(v);
                g[v].add(u);
            }
            return g;
        }

        public static int[][] parents3(List<Integer>[] g, int root) {
            int n = g.length;
            int[] par = new int[n];
            ArrayUtils.fill(par, -1);

            int[] depth = new int[n];
            depth[0] = 0;

            int[] q = new int[n];
            q[0] = root;
            for (int p = 0, r = 1; p < r; p++) {
                int cur = q[p];
                for (int nex : g[cur]) {
                    if (par[cur] != nex) {
                        q[r++] = nex;
                        par[nex] = cur;
                        depth[nex] = depth[cur] + 1;
                    }
                }
            }
            return new int[][]{par, q, depth};
        }

    }

    static class FastReader {
        private InputStream stream;
        private byte[] buf = new byte[8192];
        private int curChar;
        private int pnumChars;

        public FastReader(InputStream stream) {
            this.stream = stream;
        }

        private int pread() {
            if (pnumChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= pnumChars) {
                curChar = 0;
                try {
                    pnumChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (pnumChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = pread();
            while (isSpaceChar(c))
                c = pread();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = pread();
            }
            int res = 0;
            do {
                if (c == ',') {
                    c = pread();
                }
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = pread();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

    }

    static class Debug {
        PrintWriter out;
        boolean oj;
        boolean system;
        long timeBegin;
        Runtime runtime;

        public Debug(PrintWriter out) {
            oj = System.getProperty("ONLINE_JUDGE") != null;
            this.out = out;
            this.timeBegin = System.currentTimeMillis();
            this.runtime = Runtime.getRuntime();
        }

        public Debug() {
            system = true;
            oj = System.getProperty("ONLINE_JUDGE") != null;
            OutputStream outputStream = System.out;
            this.out = new PrintWriter(outputStream);
            this.timeBegin = System.currentTimeMillis();
            this.runtime = Runtime.getRuntime();
        }

    }
}


