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 E990 implements Runnable{
	
	int n;
	int[] dominant;
	
	boolean[] done;
	

	int adj[][];
	int[] from,to,size;

	private void solve() throws Exception {
		n = nextInt();
		size = new int[n];
		adj = new int[n][];
		from = new int[2*n-2];
		to = new int[2*n-2];
		for(int i = 0; i < n-1; i++) {
			int u = nextInt()-1;
			int v = nextInt()-1;
			from[2*i] = u;
			to[2*i] = v;
			size[u]++;
			from[2*i+1] = v;
			to[2*i+1] = u;
			size[v]++;
		}
		for(int i = 0; i < n; i++) adj[i] = new int[size[i]];
		Arrays.fill(size, 0);
		for(int i = 0; i < 2*n-2; i++) adj[from[i]][size[from[i]]++] = to[i];
		from = null;
		to = null;
		
		done = new boolean[n];
		done[0] = true;
		dominant = new int[n];
		Arrays.fill(dominant, -1);
		c = new ArrayList[n];
		p = new int[n];
		count = new int[n];
		idx = new int[n];
		for(int i = 0; i < n; i++) c[i] = new ArrayList<Integer>();
		visit(0);
		for(int i = 0; i < n; i++) out.println(dominant[i]);
	}
	
	ArrayList<Integer>[] c;
	int[] count;
	
	void dfs(int u) {
		done[u] = true;
		dominant[u] = 0;
		count[u] = 1;
		for(int v : adj[u]) {
			if(!done[v]) {
				dfs(v);
				

				ArrayList<Integer> larger = c[u];
				ArrayList<Integer> smaller = c[v];
				if(c[u].size() < c[v].size()) {
					smaller = c[u];
					larger = c[v];
					count[u] = count[v];
					dominant[u] = dominant[v];
				}
				
				int size = larger.size();
				int indexLarge = larger.size()-1;
				int indexSmall = smaller.size()-1;
				
				while(indexSmall >= 0) {
					int sum = larger.get(indexLarge)+smaller.get(indexSmall);
					larger.set(indexLarge, sum);
					if(sum > count[u] || (sum == count[u] && size-1-indexLarge < dominant[u])) {
						count[u] = sum;
						dominant[u] = size-1-indexLarge;
					}
					indexLarge--;
					indexSmall--;
				}
				c[u] = larger;
			}
		}
		c[u].add(1);
		if(count[u] <= 1) {
			count[u] = 1;
			dominant[u] = 0;
		} else if(count[u] > 1) dominant[u]++;
//		int idx = 0;
//		for(int i = 1; i < c[u].size(); i++) if(c[u].get(i) >= c[u].get(idx)) idx = i;
		
//		dominant[u] = c[u].size()-1-idx;
	}
	
	int[] idx;
	int[] p;
	
	void visit(int s){
		int u = s;
		done[u] = true;
		dominant[u] = 0;
		count[u] = 1;
		while(true){
			while(idx[u] < size[u]){
				int v = adj[u][idx[u]++];
				if(!done[v]){
					
					p[v] = u;
					u = v;
					//entered recursion
					done[v] = true;
					dominant[u] = 0;
					count[u] = 1;
				}
			}
			//end		
			c[u].add(1);
			if(count[u] <= 1) {
				count[u] = 1;
				dominant[u] = 0;
			} else if(count[u] > 1) dominant[u]++;
			//end
			
			if(u == s && idx[s] == size[s]) break;


			//leaving recursion			
			int v = u;
			u = p[u];
			//leaving recursion

			ArrayList<Integer> larger = c[u];
			ArrayList<Integer> smaller = c[v];
			if(c[u].size() < c[v].size()) {
				smaller = c[u];
				larger = c[v];
				count[u] = count[v];
				dominant[u] = dominant[v];
			}
			
			int size = larger.size();
			int indexLarge = larger.size()-1;
			int indexSmall = smaller.size()-1;
			
			while(indexSmall >= 0) {
				int sum = larger.get(indexLarge)+smaller.get(indexSmall);
				larger.set(indexLarge, sum);
				if(sum > count[u] || (sum == count[u] && size-1-indexLarge < dominant[u])) {
					count[u] = sum;
					dominant[u] = size-1-indexLarge;
				}
				indexLarge--;
				indexSmall--;
			}
			c[u] = larger;
		}
	}
	


	public static void main(String[] args) {
		new Thread(null, new E990(), "", 1<<27).start();
	}

	private BufferedReader in;
	private PrintWriter out;
	private StringTokenizer tokenizer;

	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			tokenizer = null;
			out = new PrintWriter(System.out);
			solve();
			in.close();
			out.close();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	private int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	private long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	private float nextFloat() throws IOException {
		return Float.parseFloat(nextToken());
	}

	private String nextLine() throws IOException {
		return new String(in.readLine());
	}

	private String nextToken() throws IOException {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			tokenizer = new StringTokenizer(in.readLine());
		}
		return tokenizer.nextToken();
	}


}