Description

In a remote country, there exists a unique network of libraries connected by roads. The network has some special characteristics:

1. Between any two libraries, there exists exactly one path
2. The roads never form loops or circles

The country's Ministry of Education wants to optimize their book-sharing system across these libraries. To optimize this system, they wants to know, for each library, the sum of the distances from the library to all other libraries. This information will help them place the most frequently accessed books in the most accessible locations (those with smaller total distances), while rarely requested books can be stored in the libraries far from the center (those with larger total distances).

Your task is help them find the distances.

Input

The first input line contains an integer n: the number of libraries. The libraries are numbered from $1$ to $n$
Then there are $n-1$ lines describing the roads that connects two libraries. Each line contains two integers $a_i$ and $b_i$: there is an road connecting library $a_i$ and $b_i$.

Constraints

• $1 \leq n \leq 2 \cdot 10^5$
• $1 \leq a_i, b_i \leq n$

Subtask

1. (Testcases 1-6): $n \leq 3 \cdot 10^3$
2. (Testcases 7-10): $n \leq 2 \cdot 10^5$

Output

Print $n$ integers: for each library 1, 2, $\ldots$ , $n$, the sum of the distances.

Noted that you should output one single line.

Sample Input  Download

Sample Output  Download

Tags

Discuss