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

/**
 * 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) {
                  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;
            }

      }
}


