子树大小统计

题目描述

Y 同学正在研究树形数据结构。他得到了一棵包含 $n$ 个结点的无向树，结点的编号依次为 $1$ 到 $n$。为了方便分析，Y 同学统一将编号为 $1$ 的结点指定为这棵树的根结点。

对于树中的任意一个结点 $u$，Y 同学定义其子树为：包含结点 $u$ 本身，以及所有以 $u$ 为祖先的结点构成的集合。相应地，一个结点的子树大小被定义为该子树中包含的结点总数。

请你编写程序帮助 Y 同学计算并输出这棵树中每一个结点的子树大小。

输入格式

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

接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示结点 $u$ 和结点 $v$ 之间存在一条无向边。保证输入的数据构成一棵合法的树。

输出格式

输出一行，包含 $n$ 个用空格隔开的整数。其中第 $i$ 个整数表示编号为 $i$ 的结点的子树大小。

样例

样例输入 #1

5
1 2
1 3
2 4
2 5

样例输出 #1

5 3 1 1 1

样例输入 #2

6
1 2
2 3
3 4
4 5
5 6

样例输出 #2

6 5 4 3 2 1

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le n \le 500,000$。