题目描述

给出一棵包含 $n$ 个节点的树，默认 $1$ 号节点为根节点。 对于每个节点 $i$，它的子树是指以该节点为根的所有后代节点（包括节点 $i$ 自身）构成的集合。 请你计算出每一个节点的子树中一共包含多少个节点。

输入格式

第一行包含一个整数 $n$，表示节点数。 接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示节点 $u$ 和 $v$ 之间有一条边。

输出格式

输出一行 $n$ 个整数，第 $i$ 个整数表示以节点 $i$ 为根的子树大小。整数之间用空格隔开。

输入输出样例

样例输入 1

5
1 2
1 3
3 4
3 5

样例输出 1

5 1 3 1 1

说明/提示

样例解释：

• 节点 2, 4, 5 是叶子节点，子树大小均为 1。
• 节点 3 的子树包含 {3, 4, 5}，大小为 3。
• 节点 1 是整棵树的根，包含所有节点 {1, 2, 3, 4, 5}，大小为 5。

数据范围：

• $1 \le n \le 10^5$
• 输入数据保证是一棵合法的树。