Problem Description

There is a tree with $N$ vertices numbered from $1$ to $N$. The $i$-th edge connects vertex $A_i$ and vertex $B_i$.

For this tree, the inversion number when rooted at vertex $r$ is defined as follows:

• The number of pairs $(u, v) \ (u < v)$ such that vertex $v$ is contained in the simple path from vertex $r$ to vertex $u$ or at its endpoints.

For all integers $r$ from $1$ to $N$, find the inversion number when rooted at vertex $r$.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ B_1 $ $\vdots$ $ A_{N-1} $ $ B_{N-1} $

Output Format

Output $N$ lines. The $i$-th line should contain the inversion number when rooted at vertex $i$.

Sample Input and Output

Sample Input #1

3
1 3
2 3

Sample Output #1

1
2
2

Sample Input #2

7
1 4
1 6
2 4
2 5
3 4
4 7

Sample Output #2

2
3
4
3
7
7
9

Notes/Hints

Constraints

• All input values are integers.
• $2 \leq N \leq 10^5$
• $1 \leq A_i, B_i \leq N$
• The given graph is a tree.

Sample Explanation 1

• The inversion number when rooted at vertex $1$ is $1$ from pair $(u, v) = (2, 3)$.
• The inversion number when rooted at vertex $2$ is $2$ from pairs $(u, v) = (1, 2), (1, 3)$.
• The inversion number when rooted at vertex $3$ is $2$ from pairs $(u, v) = (1, 3), (2, 3)$.

见题面 Input 部分

见题面 Output 部分