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