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*10^{5} , number of nodes on tree.Each of next N1 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
hodobox:
20181226 19:32:17
Phew, O(nlogn) passed, after I swapped the order of forcycles to avoid severe caching problems (and also binary searching my code to find a sigsegv bug, not my proudest moment) 

[Rampage] Blue.Mary:
20170807 06:15:04
My solution has complexity near O(n) (lower than O(nlogn)). 

visleck:
20170806 21:06:06
@morass isn't the intended complexity n(logn)^2 ....


morass:
20170325 00:29:06
@anonymous: Yes  sadly they are in all (mine) problems :'( Thank you for pointing out!! 

anonymous:
20170324 17:55:22
A few typos in the problem description you may want to fix:


morass:
20170224 11:22:46
@[Rampage] Blue.Mary: Sorry, you was right  one testcase was missing one edge. I've repaired it and it shall be right now! Sorry for the inconvenience!! Last edit: 20170224 11:31:31 

[Rampage] Blue.Mary:
20170224 10:19:15
Are you sure your test cases are right? 
Added by:  Morass 
Date:  20170224 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 