题目描述

给定一颗 $n$ 个节点 $n-1$ 条边的树，求出树中每个节点到其他节点的距离和。

输入格式

第一行包含一个整数 $n$（$2 \leq n \leq 10^5$），表示树的节点数。

接下来 $n-1$ 行，每行包含两个整数 $u, v$（$1 \leq u, v \leq n$），表示树的一条边。

输出格式

输出 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个节点到其他节点的距离和。

样例输入

5
1 2
1 5
2 3
2 4

样例输出

6
5
8
8
9