There are initially N−1 pairs of friends among FJ's N (2≤N≤2⋅105) cows labeled 1…N, forming a tree. The cows are leaving the farm for vacation one by one. On day i, the ith cow leaves the farm, and then all pairs of the ith cow's friends still present on the farm become friends.
For each i from 1 to N, just before the ith 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?
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N.
The next N−1 lines contain two integers ui and vi denoting that cows ui and vi are initially friends (1≤ui,vi≤N).
OUTPUT FORMAT (print output to the terminal / stdout):
The answers for i from 1 to N on separate lines.
SAMPLE INPUT:
3
1 2
2 3
SAMPLE OUTPUT:
2
0
0
(1,2,3) and (3,2,1) are the triples just before cow 1 leaves.
After cow 1 leaves, there are less than 3 cows left, so no triples are possible.
SAMPLE INPUT:
4
1 2
1 3
1 4
SAMPLE OUTPUT:
6
6
0
0
At the beginning, cow 1 is friends with all other cows, and no other pairs of cows are friends, so the triples are (a,1,c) where a,c are different cows from {2,3,4}, which gives 3⋅2=6 triples.
After cow 1 leaves, the remaining three cows are all friends, so the triples are just those three cows in any of the 3!=6 possible orders.
After cow 2 leaves, there are less than 3 cows left, so no triples are possible.
SAMPLE INPUT:
5
3 5
5 1
1 4
1 2
SAMPLE OUTPUT:
8
10
2
0
0
SCORING:
Inputs 4-5: N≤500
Inputs 6-10: N≤5000
Inputs 11-20: No additional constraints.
Problem credits: Aryansh Shrivastava, Benjamin Qi