Ada the Ladybug is visiting her friends who live on a plum tree. As many bugs like her, she has a friend in each node. She has already planned in which order she will visit them. She does that in following manner. If she is standing at a node i in the morning, she will choose shortest path to friend with number i+1. Afterward, she stays there until next morning. First day she "magically" appears on node number 1 and as she arrives at node N, she ends her journey. Your task is to find (for each node), the number of days she visited it (this means she either begins in it, ends in it or passes through it).

Input

The first line contains 1 ≤ N ≤ 4*10⁵ , number of nodes on tree.

Each of next N-1 lines contains two integers 1 ≤ I, J ≤ N, I ≠ J, the nodes which are connected by an edge.

Output

Print N lines with and integer indicating number of times i^th node was visited.

Example Input

5
1 2
2 5
2 4
5 3

Example Output

1
4
2
2
3

Example Input 2

10
1 3
1 5
5 2
5 9
9 7
9 10
6 2
4 2
8 4

Example Output 2

3
8
2
4
8
2
2
2
4
1

---

hide comments

	lalit24_04: 2023-08-11 15:46:16 can anyone explain me the first test case as it seems complicated to apply lca and binary lifting concepts to this problem? A humble request to the author of this problem is that you please provide explanations to the test case as well because nowhere I am getting solutions of spoj problems.
	mestu_paul: 2021-07-28 14:49:57 AC in one go LCA + dfs(prefix Sum)
	hodobox: 2018-12-26 19:32:17 Phew, O(nlogn) passed, after I swapped the order of for-cycles to avoid severe caching problems (and also binary searching my code to find a sigsegv bug, not my proudest moment)
	[Rampage] Blue.Mary: 2017-08-07 06:15:04 My solution has complexity near O(n) (lower than O(nlogn)).
	visleck: 2017-08-06 21:06:06 @morass isn't the intended complexity n(logn)^2 .... @blue.mary Thank you blue mary Last edit: 2017-08-07 11:45:22
	morass: 2017-03-25 00:29:06 @anonymous: Yes - sadly they are in all (mine) problems :'( Thank you for pointing out!!
	anonymous: 2017-03-24 17:55:22 A few typos in the problem description you may want to fix: s/done/node s/though/through s/aperas/appears s/magicaly/magically
	morass: 2017-02-24 11:22:46 @[Rampage] Blue.Mary: Sorry, you was right - one test-case was missing one edge. I've repaired it and it shall be right now! Sorry for the inconvenience!! Last edit: 2017-02-24 11:31:31
	[Rampage] Blue.Mary: 2017-02-24 10:19:15 Are you sure your test cases are right?