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.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Edu_47F implements Runnable {

	public static void main(String[] args) throws IOException {
		new Thread(null, new Edu_47F(), "Main", 1 << 28).start();
	}

	ArrayList<Integer>[] aList;

	static int[] mCnt;
	static int[] mRDep;

	static ArrayList<Integer>[] cnts;

	public void run() {
		try {
			BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
			PrintWriter printer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
			int nV = Integer.parseInt(reader.readLine());
			aList = new ArrayList[nV];

			for (int i = 0; i < nV; i++) {
				aList[i] = new ArrayList<Integer>();
			}

			for (int i = 0; i < nV - 1; i++) {
				StringTokenizer inputData = new StringTokenizer(reader.readLine());
				int a = Integer.parseInt(inputData.nextToken()) - 1;
				int b = Integer.parseInt(inputData.nextToken()) - 1;
				aList[a].add(b);
				aList[b].add(a);
			}

			mCnt = new int[nV];
			mRDep = new int[nV];
			cnts = new ArrayList[nV];

			dfs(0, -1);

			for (int i = 0; i < nV; i++) {
				printer.println(mRDep[i]);
			}
			printer.close();
		} catch (Exception e) {

		}
	}

	void dfs(int cV, int pV) {
		int mCDepth = 0;
		int mC = -1;

		for (int aV : aList[cV]) {
			if (aV != pV) {
				dfs(aV, cV);
				if (cnts[aV].size() > mCDepth) {
					mCDepth = cnts[aV].size();
					mC = aV;
				}
			}
		}

		if (mC == -1) {
			cnts[cV] = new ArrayList<>();
			cnts[cV].add(1);
			mCnt[cV] = 1;
			mRDep[cV] = 0;
			return;
		}

		ArrayList<Integer> pCnts = cnts[mC];
		int pMCnt = mCnt[mC];
		int pMRDep = mRDep[mC];

		for (int aV : aList[cV]) {
			if (aV != pV && aV != mC) {
				ArrayList<Integer> tMerge = cnts[aV];

				for (int i = 0; i < tMerge.size(); i++) {
					int nVal = pCnts.get(pCnts.size() - 1 - i) + tMerge.get(tMerge.size() - 1 - i);
					pCnts.set(pCnts.size() - 1 - i, nVal);
					if (nVal > pMCnt || (nVal == pMCnt && i < pMRDep)) {
						pMCnt = nVal;
						pMRDep = i;
					}
				}
			}
		}

		pCnts.add(1);
		pMRDep++;

		if (1 >= pMCnt) {
			pMCnt = 1;
			pMRDep = 0;
		}

		cnts[cV] = pCnts;
		mCnt[cV] = pMCnt;
		mRDep[cV] = pMRDep;
	}

}
