Andrew recently bought a new motorbike and wants to try it out on the roads of TreeLand.As the name suggests, Treeland is in the shape of a Tree , i.e , it is an undirected acyclic graph. Treeland has n junctions connected by n-1 roads. It is guaranteed that treeland is connected , i.e , any two junctions are reachable from each other. Andrew is at junction number 1. Andrew wants to ride his bike on a valid path from junction number 1 to another junction (he may even come back to junction number 1).A valid path is one which visits any given junction atmost 2 times.

There is another constraint for the movement of Andrew on his bike . Let us root the tree at node number 1 . Let d(u) be the distance of u from node number 1 . Andrew is said to be going down if he moves from an ancestor of u to u directly . Similarly Andrew is said to be going up if he moves from u to an ancestor of u directly .

Initially when Andrew is at node 1 he moves in the downward direction . Later he may change his direction to upward . However he cannot change it back to downward , i.e , on a valid path Andrew's direction can change atmost once .

For all v from 1 to n , tell Andrew the number of valid paths from junction numbered 1 to junction numbered v.

Note that a path must involve Andrew crossing non zero number of edges . Thus , a path beginning at junction number 1 and ending at junction number 1 , cannot be only the vertex 1 . It must visit some another node and then return back to 1.

Input
The first line contains a number n denoting the number of junctions.
The next n-1 lines contain a pair of integers u v denoting there is a road between junction numbered u and junction numbered v.

Output
Print n space separated integers where the v^th integer denotes the number of valid paths from junction numbered 1 to junction numbered v.

Constraints
1 ≤ n ≤ 10^5
1 ≤ u,v ≤ n
There are no self-loops or multiple edges and it is guaranteed that the tree is connected.

Note: A road between u and v means one can travel from u to v and vice versa.

SAMPLE INPUT
6
1 4
4 2
3 4
4 5
5 6

SAMPLE OUTPUT
5 1 1 5 2 1

Explanation

For v=4,the paths are {1,4} , {1,4,3,4} , {1,4,2,4} , {1,4,5,4} and {1,4,5,6,5,4}.
Note for v=1 the path {1} is not counted.

见题面

见题面