题目描述

有一棵 $n$ 个点的树，请求出每个点到其他所有点的距离的和。

定义两个点的距离为它们的简单路径上经过了多少条边。

输入格式

第一行一个整数 $n$ 表示点的数目。

接下来 $n−1$ 行，每行两个整数 $x,y$ 描述一条树边。

输出格式

输出共 $n$ 行。

第 $i$ 行表示编号为 $i$ 的点到其他所有点的距离的和。

Samples

5
1 2
1 5
2 3
2 4

6
5
8
8
9

数据规模

对于所有数据，保证 $2≤n≤10^5,1≤x,y≤n$。

数据保证读入的是一棵树。