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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Iterator;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.function.Consumer;
import java.util.Map;
import java.util.Map.Entry;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        MyScan in = new MyScan(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskF solver = new TaskF();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskF {
        public void solve(int testNumber, MyScan in, PrintWriter out) {
            int n = in.nextInt();


            int[] res = new int[n];
            TaskF.Level[] em = new TaskF.Level[n];
            Tree tree = TreeReader.byEdges(n, in);

            tree.setOnRemove((l) -> {
                if (em[l[0]] == null) {
                    em[l[0]] = new TaskF.Level();

                }
                em[l[0]].add(l[1], 1);
                res[l[0]] = em[l[0]].max - l[1];

                if (l[2] >= 0) {
                    if (em[l[2]] == null) {
                        em[l[2]] = em[l[0]];
                    } else {
                        em[l[2]] = em[l[0]].merge(em[l[2]]);
                    }
                }
            });


            tree.dfs(0);

            out.println(new AList(res));
        }

        private static final class Level {
            private final HashMap<Integer, Integer> lvl = new HashMap<>();
            private int max;

            public void add(int index, int val) {
                Integer newV = lvl.merge(index, val, Math::addExact);
                Integer om = lvl.getOrDefault(max, 0);
                if (newV > om || newV.equals(om) && index < max) {
                    max = index;
                }
            }

            public TaskF.Level merge(TaskF.Level level) {
                if (level.lvl.size() > lvl.size()) {
                    return level.add(this);
                } else {
                    return this.add(level);
                }
            }

            private TaskF.Level add(TaskF.Level level) {
                for (Map.Entry<Integer, Integer> x : level.lvl.entrySet()) {
                    add(x.getKey(), x.getValue());
                }
                return this;
            }

        }

    }

    static class MyScan {
        private final InputStream in;
        private byte[] inbuf = new byte[1024];
        public int lenbuf = 0;
        public int ptrbuf = 0;

        public MyScan(InputStream in) {
            this.in = in;
        }

        private int readByte() {
            if (lenbuf == -1) throw new InputMismatchException();
            if (ptrbuf >= lenbuf) {
                ptrbuf = 0;
                try {
                    lenbuf = in.read(inbuf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (lenbuf <= 0) return -1;
            }
            return inbuf[ptrbuf++];
        }

        public int nextInt() {
            int num = 0, b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }

            while (true) {
                if (b >= '0' && b <= '9') {
                    num = num * 10 + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

    }

    static class TreeReader {
        public static Tree byEdges(int l, MyScan sc) {
            return new Tree(tr1(l, sc));
        }

        private static int[][] tr1(int n, MyScan sc) {
            int[][] x = new int[2][n - 1];
            for (int i = 0; i < n - 1; i++) {
                x[0][i] = sc.nextInt() - 1;
                x[1][i] = sc.nextInt() - 1;
            }
            return pn(x, n);
        }

        public static int[][] pn(int[][] x, int n) {
            int[] ct = new int[n];
            int[][] res = new int[n][];
            for (int v : x[0]) {
                ct[v]++;
            }
            for (int v : x[1]) {
                ct[v]++;
            }
            for (int l = 0; l < n; l++) {
                res[l] = new int[ct[l]];
            }
            for (int i = 0; i < x[0].length; i++) {
                res[x[0][i]][--ct[x[0][i]]] = x[1][i];
                res[x[1][i]][--ct[x[1][i]]] = x[0][i];
            }
            return res;
        }

    }

    static class Tree {
        public int[][] data;
        Consumer<int[]> onAdd;
        Consumer<int[]> onRemove;

        public Tree(int[][] data) {
            this.data = data;
        }

        public void setOnRemove(Consumer<int[]> onRemove) {
            this.onRemove = onRemove;
        }

        private int[] dfs(int start, Consumer<int[]> onAdd, Consumer<int[]> onRemove) {
            Tree.P[] n = new Tree.P[data.length * 2];
            int toVisit = 0;
            n[toVisit++] = new Tree.P(start, true, -1);
            boolean[] vis = new boolean[data.length];
            vis[start] = true;
            int[] level = new int[data.length];
            while (toVisit > 0) {
                Tree.P ppr = n[--toVisit];
                if (!ppr.b) {
                    if (onRemove != null)
                        onRemove.accept(new int[]{ppr.ind, level[ppr.ind], ppr.parent});
                    continue;
                }
                ppr.b = false;
                int i = ppr.ind;
                n[toVisit++] = ppr;
                if (onAdd != null)
                    onAdd.accept(new int[]{ppr.ind, level[ppr.ind], ppr.parent});
                for (int kk : data[i]) {
                    if (!vis[kk]) {
                        vis[kk] = true;
                        level[kk] = level[i] + 1;
                        n[toVisit++] = new Tree.P(kk, true, i);
                    }
                }
            }
            return level;
        }

        public int[] dfs(int start) {
            return dfs(start, onAdd, onRemove);
        }

        public static class P {
            private boolean b;
            private final int ind;
            private final int parent;

            public P(int i, boolean b, int par) {
                this.ind = i;
                this.b = b;
                this.parent = par;
            }

        }

    }

    static class AList implements Iterable<Integer> {
        int[] data;
        int size = 0;

        public AList(int n) {
            this.data = new int[Math.max(Integer.highestOneBit(n - 1) << 1, 4)];
        }

        public AList() {
            this(4);
        }

        public AList(int[] data) {
            this(data.length);
            System.arraycopy(data, 0, this.data, 0, data.length);
            size = data.length;
        }

        AList(int[] data, int s) {
            this.data = data;
            this.size = s;
        }


        public Iterator<Integer> iterator() {


            int[] m = new int[1];
            return new Iterator<Integer>() {

                public boolean hasNext() {
                    return m[0] < AList.this.size;
                }


                public Integer next() {
                    return AList.this.data[m[0]++];
                }
            };
        }


        public String toString() {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < size; i++) {
                sb.append(data[i]).append(' ');
            }
            return sb.toString();
        }

    }
}

