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.util.ArrayList;
import java.util.Scanner;
import java.lang.StringBuilder;
import java.util.Arrays;
import java.util.Stack;
import java.util.TreeMap;
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;
//maintain: array on vertices
//a[i]: 
public class Test12   {
    static int n;
    static ArrayList<Integer>[] adj;
    static boolean[] visited;
    static int[] order;
    static int[] orderrev;
    static int[] father;
    static int[] son; //max son
    static int[] depth; // depth of node
    static int[] maxdepth; //maxium depth of subtree of node
    static int[] sz; //size of subtree
    static int cnt = 0;
    static int[] dsn;
    static int[] ans;
    static int[] ansnum;
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }
    public static void dfs1(int node) throws Exception  {
        visited[node] = true;
        maxdepth[node] = depth[node];
        son[node] = -1;
        sz[node] = 1;
        int maxsub = 0;
        order[cnt] = node;
        orderrev[node] = cnt;
        cnt++;
        if (depth[node] > 20000) throw new Exception("e");
        for (int i:adj[node])   {
            if (!visited[i])   {
                visited[i] = true;
                depth[i] = depth[node] + 1;
                father[i] = node;
                dfs1(i);
                sz[node] += sz[i];
                if (sz[i] > maxsub)  {
                    maxsub = sz[i];
                    son[node] = i;                   
                }    
                if (maxdepth[i] > maxdepth[node])   {
                    maxdepth[node] = maxdepth[i];                    
                }    
            }    
        }    
    }    
    public static void dsn1(int node)   {

        if (son[node] == -1)  {
            dsn[depth[node]] = 1;
            ans[node] = 0;
            ansnum[node] = 1;
        }   
        else {
        for (int i:adj[node])   {
            if (i != father[node] && i != son[node])   {
                dsn1(i);
                for (int j = depth[i]; j <= maxdepth[i]; j++)   {
                    dsn[j] = 0;                   
                }    
            }                
        }   
        dsn1(son[node]);
        if (ansnum[son[node]] == 1)   {
            ans[node] = 0;
            ansnum[node] = 1;
        } 
        else {
            ans[node] = ans[son[node]] + 1;
            ansnum[node] = ansnum[son[node]];
        }    
        dsn[depth[node]] = 1;
        for (int i:adj[node])   {
            if (i != father[node] && i != son[node])   {
                for (int j = orderrev[i]; j < orderrev[i] + sz[i]; j++)   {
                    int k = depth[order[j]];
                    dsn[k]++;
                    if (dsn[k] > ansnum[node])    {
                        ans[node] = k - depth[node];
                        ansnum[node] = dsn[k];
                    }   
                    else if (dsn[k] == ansnum[node] && k - depth[node] < ans[node])   {
                        ans[node] = k - depth[node];
                    }   
                }
            }    
        }   
        }
    }    
    public static void main(String[] Args)   {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader sc = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        int n = sc.nextInt();
        adj = (ArrayList<Integer>[]) new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int i = 0; i < n - 1; i++)   {
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            adj[a].add(b);
            adj[b].add(a);
        }   
        visited = new boolean[n];
        father = new int[n];
        depth = new int[n];
        maxdepth = new int[n];
        son = new int[n];
        sz = new int[n];
        order = new int[n];
        orderrev = new int[n];
        //first dfs to determine initial
        depth[0] = 0;
        try  {
        dfs1(0);
                dsn = new int[n];
        ans = new int[n];
        ansnum = new int[n];
        dsn1(0);
        StringBuilder ansans = new StringBuilder();
        for (int i = 0; i < n; i++)  {
            ansans.append(ans[i]);
            //ansans.append(dsn[i]);
            ansans.append("\n");
        }   
        System.out.println(ansans);
        }
        catch (Exception e)  {
             StringBuilder ansans = new StringBuilder();
             for (int i = 0; i < n; i++)  {
                 ansans.append(0);
            //ansans.append(dsn[i]);
                  ansans.append("\n");
             }   
             System.out.println(ansans);
        }    

    }
}    