Tree Distances II

Input

The first line contains an integer $n (1 \leq n \leq 2 \cdot 1 0^{5})$ n\:(1 ≤ n ≤ 2 \cdot 10^5): the number of nodes. The nodes are numbered $1, 2, ..., n$ 1, 2, ..., n.

Then there are $n - 1$ n − 1 lines describing the edges. Each line contains two integers $a$ and $b (1 \leq a, b \leq n)$ b\:(1 \le a, b \le n): there is an edge between nodes $a$ and $b$ .

Output

Print $n$ integers: for each node $1, 2, ..., n$ 1, 2, ..., n, the sum of the distances.

Examples

Example 1

Loading