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.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

public class F {
//
	static int N;
	static ArrayList<Integer> children[];
	static HashMap<Integer, Integer> res[];
	static int answer[];
	static int dep[];
	public static void main(String args[]) {
		new Thread(null, () -> asdf(args), "lmao", 1<<28).start();
	}
	public static void asdf(String[] args) {
		JS in = new JS();
		PrintWriter out = new PrintWriter(System.out);
		
		N = in.nextInt();
		ArrayList<Integer> adj[] = new ArrayList[N];
		children = new ArrayList[N];
		for(int i = 0; i < N; i++) {
			adj[i] = new ArrayList<Integer>();
			children[i] = new ArrayList<Integer>();
		}
		
		for(int i = 0; i < N-1; i++) {
			//int v1 = i;
			//int v2 = i+1;
			int v1 = in.nextInt()-1;
			int v2 = in.nextInt()-1;
			adj[v1].add(v2);
			adj[v2].add(v1);
		}
		
		boolean vis[] = new boolean[N];
		dep = new int[N];
		dep[0] = 0;
		vis[0]=true;
		que q = new que(N+1);
		que depQ = new que(N+1);
		q.add(0);
		depQ.add(0);
		while(!q.isEmpty()) {
			int v = q.poll();
			int d = depQ.poll();
			for(Integer ii : adj[v]) {
				if(vis[ii])continue;
				children[v].add(ii);
				q.add(ii);
				vis[ii]=true;
				dep[ii] = d+1;
				depQ.add(d+1);
			}
		}

		res = new HashMap[N];
		for(int i = 0; i < N; i++) res[i] = new HashMap<Integer, Integer>();
		answer = new int[N];
		Arrays.fill(answer, -1);
		dfs(0);
		
		for(int i = 0; i < N; i++) {
			out.println(answer[i]-dep[i]);
		}
		out.close();
		
		
	}

	
	static void dfs(int node) {
		if(children[node].size() == 0) {
			HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
			map.put(dep[node], 1);
			res[node] = map;
			answer[node] = dep[node];
		}
		else {
			int bigId = -1;
			int sz = -1;
			int curDep = -1;
			int curDepRes = -1;
			HashMap<Integer, Integer> map = null;
			for(Integer ii : children[node]) {
				dfs(ii);
				if(res[ii].size() > sz) {
					map = res[ii];
					bigId = ii;
					sz = res[ii].size();
					curDep = answer[ii];
					curDepRes = res[ii].get(curDep);
				}
			}
			for(Integer ii : children[node]) {
				if(ii==bigId)continue;
				for(Integer key : res[ii].keySet()) {
					int have = res[ii].get(key);
					map.put(key, map.getOrDefault(key, 0)+have);
					if(map.get(key) > curDepRes) {
						curDep = key;
						curDepRes = map.get(key);
					}
					else if(map.get(key) == curDepRes) {
						if(key < curDep) curDep = key;
					}
				}
				res[ii].clear();
			}
			map.put(dep[node], 1);
			if(curDepRes == 1) curDep = dep[node];
			res[node] = map;
			answer[node] = curDep;			
		}
	}
	
	static class que{
		int ar[];
		int cur;
		public que(int n) {
			ar = new int[n];
			cur = 0;
		}
		public void add(int x) {
			ar[cur]=x;
			cur++;
		}
		public int poll() {
			int ret = ar[cur-1];
			cur--;
			return ret;
		}
		public boolean isEmpty() {
			return cur==0;
		}
	}
	
	static class JS{
		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 JS() {
			in = new BufferedInputStream(System.in, BS);
		}
		
		public JS(String s) throws FileNotFoundException {
			in = new BufferedInputStream(new FileInputStream(new File(s)), 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;
			}
		}
	}
}
