题目描述

Grammy 有一棵包含 $n$ 个顶点的树，顶点编号为 $1,2,\ldots,n$。

对于每一个顶点 $r$，分别将这棵树以 $r$ 为根。

Grammy 想知道：有多少个无序点对 $(x,y)$，使得 $x$ 和 $y$ 的最近公共祖先为 $z$，并满足

这里的无序点对允许两个端点相同，即可以认为需要统计所有满足

的点对。

请对每一个可能的根分别计算答案。

输入格式

第一行包含一个整数 $n$，表示树的顶点数。

接下来 $n-1$ 行，每行包含两个整数 $u_i,v_i$，表示树中存在一条连接顶点 $u_i$ 和顶点 $v_i$ 的边。

输出格式

输出 $n$ 行。

第 $i$ 行输出一个整数，表示以顶点 $i$ 为根时，满足条件的无序点对数量。

样例

输入：
5
1 2
4 2
2 5
3 5

输出：
15
15
15
15
14