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.*;
import java.util.*;

public class Main{
	static int[][]adj;
	static int[]size;
	static int[]ans;
	static int[]par;
	static ArrayList<Integer>occofocc[];
	static int[]maxo,maxoo;
	static void dfs(int i) {
		size[i]=0;
		int maxChild=-1,maxSize=-1;
		int maxOcc=0,maxOccOfOcc=1;
		for(int o=0;o<adj[i].length;o++) {
			int j=adj[i][o];
			int p=par[i];
			if(j==p)continue;
			size[i]+=size[j];
			if(occofocc[j].size()>maxSize) {
				maxSize=occofocc[j].size();
				maxChild=j;
			}
		}
		if(maxChild==-1) {
			occofocc[i]=new ArrayList<Integer>();
			occofocc[i].add(1);
			ans[i]=0;
			maxo[i]=maxOcc+1;
			maxoo[i]=maxOccOfOcc;
			return;
		}
		occofocc[i]=occofocc[maxChild];
		if(maxoo[maxChild]>maxOccOfOcc || (maxoo[maxChild]==maxOccOfOcc && maxo[maxChild]<maxOcc)) {
			maxOccOfOcc=maxoo[maxChild];
			maxOcc=maxo[maxChild];
		}
		for(int o=0;o<adj[i].length;o++) {
			int j=adj[i][o],p=par[i];
			if(j==p || j==maxChild)continue;
			for(int z=occofocc[j].size()-1,x=0;z>=0;z--,x++) {
				int curoccofocc=occofocc[j].get(z);
				int curx=x+1;
				int newoccofocc=occofocc[i].get(occofocc[i].size()-1-x)+curoccofocc;
				occofocc[i].set(occofocc[i].size()-1-x, newoccofocc);
				if(newoccofocc>maxOccOfOcc || (newoccofocc==maxOccOfOcc && curx<maxOcc)) {
					maxOccOfOcc=newoccofocc;
					maxOcc=curx;
				}	
			}
		}
		occofocc[i].add(1);
		ans[i]=maxOcc;
		maxo[i]=maxOcc+1;
		maxoo[i]=maxOccOfOcc;
	}
	static int[]lvl;
	static void dfs(int i,int p) {
		par[i]=p;
		for(int j:adj[i]) {
			if(j==p)continue;
			lvl[j]=1+lvl[i];
			dfs(j, i);
		}
	}
	static void main() throws Exception{
		int n=sc.nextInt();
		int[]sizes=new int[n];
		int[][]edges=new int[n-1][];
		occofocc=new ArrayList[n];
		adj=new int[n][];
		for(int i=0;i<n-1;i++) {
			int x=sc.nextInt()-1,y=sc.nextInt()-1;
			sizes[x]++;
			sizes[y]++;
			edges[i]=new int[] {x,y};
		}
		for(int i=0;i<n;i++) {
			adj[i]=new int[sizes[i]];
		}
		for(int i=0;i<n-1;i++) {
			int x=edges[i][0],y=edges[i][1];
			adj[x][--sizes[x]]=y;
			adj[y][--sizes[y]]=x;
		}
		size=new int[n];
		ans=new int[n];
		maxo=new int[n];
		maxoo=new int[n];
		lvl=new int[n];
		par=new int[n];
		dfs(0, -1);
		Integer[]arr=new Integer[n];
		for(int i=0;i<n;i++) {
			arr[i]=i;
		}
		Arrays.sort(arr,(x,y)->lvl[y]-lvl[x]);
		for(int i=0;i<n;i++) {
			dfs(arr[i]);
		}
		pw = new PrintWriter(System.out);
		for(int i=0;i<n;i++) {
			pw.println(ans[i]);
		}
    }
    public static void main(String[] args) throws Exception{
    	sc=new MScanner(System.in);
//        int tc=1;
//        tc=sc.nextInt();
//        for(int i=1;i<=tc;i++) {
//            pw.printf("Case #%d: ", i);
            main();
//        }
        pw.flush();
    }
    static PrintWriter pw;
    static MScanner sc;
    static class MScanner {
        StringTokenizer st;
        BufferedReader br;
        public MScanner(InputStream system) {
            br = new BufferedReader(new InputStreamReader(system));
        }
     
        public MScanner(String file) throws Exception {
            br = new BufferedReader(new FileReader(file));
        }
     
        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
        public int[] intArr(int n) throws IOException {
            int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
            return in;
        }
        public long[] longArr(int n) throws IOException {
            long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
            return in;
        }
        public int[] intSortedArr(int n) throws IOException {
            int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
            shuffle(in);
            Arrays.sort(in);
            return in;
        }
        public long[] longSortedArr(int n) throws IOException {
            long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
            shuffle(in);
            Arrays.sort(in);
            return in;
        }
        public Integer[] IntegerArr(int n) throws IOException {
            Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
            return in;
        }
        public Long[] LongArr(int n) throws IOException {
            Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
            return in;
        }
        public String nextLine() throws IOException {
            return br.readLine();
        }
     
        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
     
        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
     
        public char nextChar() throws IOException {
            return next().charAt(0);
        }
     
        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }
     
        public boolean ready() throws IOException {
            return br.ready();
        }
     
        public void waitForInput() throws InterruptedException {
            Thread.sleep(3000);
        }
        
    }
    static void sort(int[]in) {
    	shuffle(in);
        Arrays.sort(in);
    }
    static void sort(long[]in) {
    	shuffle(in);
        Arrays.sort(in);
    }
    static void shuffle(int[]in) {
        for(int i=0;i<in.length;i++) {
            int idx=(int)(Math.random()*in.length);
            int tmp=in[i];
            in[i]=in[idx];
            in[idx]=tmp;
        }
    }
    static void shuffle(long[]in) {
        for(int i=0;i<in.length;i++) {
            int idx=(int)(Math.random()*in.length);
            long tmp=in[i];
            in[i]=in[idx];
            in[idx]=tmp;
        }
    }
}