题目描述

给你一个包含 $n$ 个节点的有根树。树上节点编号从 $1$ 到 $n$。根节点编号为 $1$。

对于树上每个节点 $i(1 \le i \le n)$，求：以节点 $i$ 为根的子树大小（即该子树包含的节点数）。

输入格式

第一行，一个整数 $n(1 \le n \le 10^5)$。

接下来 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$，表示树上一条边连接的两个端点（$1 \le u_i, v_i \le n$，$u_i \neq v_i$）。

输出格式

输出共 $n$ 行，每一行包含一个整数。

其中，第 $i$ 行的整数表示以节点 $i$ 为根的子树大小。

样例

3
1 2
1 3

3
1
1

6
1 2
2 3
3 6
4 1
5 3

6
4
3
1
1
1

说明/提示

数据规模与约定

• 对于 $20\%$ 的数据，$n \le 10$；
• 对于 $40\%$ 的数据，$n \le 1000$；
• 对于 $100\%$ 的数据，$1 \le n \le 10^5$。数据保证这是一棵树。