Cow Friendship Triplets

There are initially $N-1$ pairs of friends among FJ's $N$ cows labeled $1\dots N$, forming a tree. The cows leave the farm 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, determine the number of ordered triples of distinct cows $(a,b,c)$ such that none of $a$, $b$, $c$ are on vacation, $a$ is friends with $b$, and $b$ is friends with $c$.

inputFormat

The first line contains a single integer $N$ -- the number of cows.

The following $N-1$ lines each contain two integers $u$ and $v$ indicating that cow $u$ and cow $v$ are initially friends. It is guaranteed that these pairs form a tree.

outputFormat

Output $N$ lines. The $i$th line should contain the number of ordered triples of distinct cows $(a,b,c)$ satisfying the condition just before the $i$th cow leaves.

sample

3
1 2
2 3

2
0
0