该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

石老板加入了美团外卖后，做了一个梦：

他成为了皇帝，将管理这 $n$ 个城市构成的国家。这些城市由 $n-1$ 条边连通形成一棵树，但并没有确定一个首都（根结点）。

石老板希望通过树链剖分的形式，把城市划分成若干个部分。

一个有根树的树链剖分为将整棵树划分成若干条从一个点到这个点的祖先（包括本身）的链，并且这些链没有公共点。如果一条边在某条链上，即这条边的两个端点在同一个链上，那么这个边为重边，否则为轻边。

一个树链剖分的代价为所有点对的路径上轻边的个数之和。这里将 $(u,v)$ 和 $(v,u)$ 当成同一个点对。一个有根树的最优树链剖分为所有方案中代价最小的方式，请求出每个点为根对应的有根树的最优树链剖分的代价。

最后，他希望他的子民人人都能吃得起外卖。

输入格式

第一行，两个整数 $n$，表示结点个数。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示一条边。

输出格式

$n$ 行，第 $i$ 行表示以 $i$ 为根的最优树链剖分的代价。

样例输入

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

样例输出

28
21
21
21
33
26
28
21

数据范围与提示

共 $10$ 组数据

测试点 $1,2,3$ 满足 $1\le n\le 15$ 。

测试点 $4,5,6$ 满足 $n\le 1000$。

对于 $100\%$ 的数据，满足 $1\le n\le 10^5$。

点我下载样例2输入文件

点我下载样例2输出文件