Given a tree, it is wanted to know for each node the sum of the distances from it to the remaining ones.

Input

A line containing a single integer ~N~ (~N \le 100000~), the amount of nodes in the tree. ~N - 1~ lines representing the edges of the tree.

Output

~N~ lineas, the ith line must contain the sum of the distances from all nodes to the ~i-th~ one.

Input Sample

3
1 2
2 3

Output Sample

3
2
3