Given a tree of ~n~ nodes in which node ~0~ is root. Your task is to print out the number of nodes in all subtrees.

Input

• The first line contains an integer ~n~ ~(0 < n ≤ 10^5)~.
• Each of the next ~n-1~ lines contains two integers ~a, b~ representing an edge that connects vertex ~a~ and vertex ~b~ ~(0 ≤ a, b < n)~.

Output

• For each node ~V~ in the tree in ascending order, output the number of nodes in subtree in which ~V~ is the root.

Example Input

6 
0 1
0 2
2 3
2 4
1 5

Example Output:

0 6
1 2
2 3
3 1
4 1
5 1

Note

• https://drive.google.com/file/d/1X6H7qsDtMpeeb0OoSlZoLlRZt3qnGc_O/view?usp=sharing