You are given a tree consisting of n nodes.
Your task is to determine for each node the sum of the distances from the node to all other nodes.
### Input
- The first line contains an integer n.
- The next n−1 lines, each line contains 2 integers u and v, there is an edge between u and v.
### Output
- Print n integers: for each node from 1 to n, the sum of the distances.
### Constraints
- 1≤n≤105.
- 1≤u,v≤n.
### Example
Input:
512133435
Output:
69588
