문제

There are initially $N-1$ pairs of friends among FJ's $N$ ($2\le N\le 2\cdot 10^5$) cows labeled $1\dots N$, forming a tree. The cows are leaving the farm for vacation one by one. On day $i$, the $i$th cow leaves the farm, and then all pairs of the $i$th cow's friends still present on the farm become friends.

For each $i$ from $1$ to $N$, just before the $i$th cow leaves, how many ordered triples of distinct cows $(a,b,c)$ are there such that none of $a,b,c$ are on vacation, $a$ is friends with $b$, and $b$ is friends with $c$?

입력

The first line contains $N$.

The next $N-1$ lines contain two integers $u_i$ and $v_i$ denoting that cows $u_i$ and $v_i$ are initially friends ($1\le u_i,v_i\le N$).

출력

The answers for $i$ from $1$ to $N$ on separate lines.

예제 입력 1

3
1 2
2 3

예제 출력 1

2
0
0

예제 입력 2

4
1 2
1 3
1 4

예제 출력 2

6
6
0
0

예제 입력 3

5
3 5
5 1
1 4
1 2

예제 출력 3

8
10
2
0
0

점수

Inputs 4-5: $N\le 500$Inputs 6-10: $N\le 5000$Inputs 11-20: No additional constraints.