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 F implements Runnable {
	public static void main (String[] args) {new Thread(null, new F(), "_cf", 1 << 28).start();}

	int n;
	int[] size, par, bigKid, depth, res;
	int[][] adj;
	int[] freq, maxID;
	IntList[] who;
	
	public void run() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("");

		n = fs.nextInt();
		readTree(fs);
		
		size = new int[n];
		par = new int[n];
		bigKid = new int[n];
		depth = new int[n];
		int[] q = new int[n];
		
		int tail = 1;
		for(int i = 0; i < tail; i++) {
			int u = q[i];
			for(int v : adj[u]) {
				if(v == par[u]) continue;
				par[v] = u;
				depth[v] = 1+depth[u];
				q[tail++] = v;
			}
		}
		for(int i = tail-1; i >= 0; i--) {
			int u = q[i];
			size[u]++;
			bigKid[u] = -1;
			for(int j = 0; j < adj[u].length; j++) {
				int v = adj[u][j];
				if(v == par[u]) continue;
				size[u] += size[v];
				if(bigKid[u] == -1) bigKid[u] = j;
				else {
					int s1 = size[adj[u][bigKid[u]]];
					if(s1 < size[v]) bigKid[u] = j;
				}
			}
		}
		
		res = new int[n];
		who = new IntList[n];
		freq = new int[n];
		maxID = new int[n];
		
		solve(0, false);

		for(int i : res) out.println(i);
		
		out.close();
	}
	
	void solve(int u, boolean undo) {
		for(int j = 0; j < adj[u].length; j++) if(j != bigKid[u]) {
			if(adj[u][j] == par[u]) continue;
			solve(adj[u][j], true);
		}
		if(bigKid[u] == -1) {
			who[u] = new IntList();
			maxID[u] = -1;
		}
		else {
			int big = adj[u][bigKid[u]];
			solve(big, false);
			maxID[u] = maxID[big];
			who[u] = who[big];
		}
		who[u].add(depth[u]);
		update(depth[u], u);
		
		for(int j = 0; j < adj[u].length; j++) if(j != bigKid[u]) {
			int v = adj[u][j];
			if(v == par[u]) continue;
			for(int k = 0; k < who[v].size(); k++) {
				update(who[v].get(k), u);
				who[u].add(who[v].get(k));
			}
		}
		
		res[u] = maxID[u]-depth[u];
		
		if(undo) {
			for(int k = 0; k < who[u].size(); k++) {
				freq[who[u].get(k)]--;
			}
		}
		
	}
	
	void update(int val, int from) {
		freq[val]++;
		if(maxID[from] == -1) maxID[from] = val;
		else if(freq[val] > freq[maxID[from]]) maxID[from] = val;
		else if(freq[val] == freq[maxID[from]] && val < maxID[from]) maxID[from] = val;
	}
	
	void readTree(FastScanner fs) {
		int[] deg = new int[n];
		int[] us = new int[n-1], vs = new int[n-1];
		for(int i = 0; i < n-1; i++) {
			us[i] = fs.nextInt()-1;
			vs[i] = fs.nextInt()-1;
			deg[us[i]]++; deg[vs[i]]++;
		}
		adj = new int[n][];
		for(int i = 0; i < n; i++) {
			adj[i] = new int[deg[i]];
			deg[i] = 0;
		}
		for(int i = 0; i < n-1; i++) {
			int u = us[i], v = vs[i];
			adj[u][deg[u]++] = v;
			adj[v][deg[v]++] = u;
		}
	}
	
	class IntList {
		int[] EMPTY = {};
		int n = 0, a[] = EMPTY;
		void add(int v) {
			if (n >= a.length)
				a = Arrays.copyOf(a, (n << 2) + 8);
			a[n++] = v;
		}
		int get(int idx) { return a[idx]; }
		int size() { return n; }
	}

	class FastScanner {
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public FastScanner() {
			in = new BufferedInputStream(System.in, BS);
		}

		public FastScanner(String s) {
			try {
				in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
			}
			catch (Exception e) {
				in = new BufferedInputStream(System.in, BS);
			}
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}                
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
		
		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}
		
	}

}