ADAVISIT - Ada and Plum


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 planed 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" apears 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*105 , 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 ith 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
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?


Added by:Morass
Date:2017-02-24
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All