Again Saitama is bored!! And this time he decides that he will  play a game. Given is a tree of n nodes. For every node i ($1 \le i \le n$) he wants to find out the sum of distances of all the other nodes from the i-th node. Since he is not very good in solving tree-related problems, he has asked you to do it instead. Can you solve the problem.

Input format

• First line contains single integer n.
• next n-1 lines contain two integers x and y.

Output format

• Print n integers, the i-th integer is the sum of distances of all other nodes from i-th node.

Constraints

• $1 \le n \le 2*10^4$
• $1 \le x, y \le n$