题目描述

给定一棵包含 $n$ 个结点的树，结点编号为 $1 \sim n$。我们将 $1$ 号结点指定为这棵树的根。

对于树中的任意一个结点 $u$，定义其 子树 为 $u$ 本身以及所有以 $u$ 为祖先的结点集合。子树大小 定义为该子树中包含的结点总数。

请你计算并输出这棵树中每个结点的子树大小。

输入格式

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

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

输出格式

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

5
1 2
1 3
2 4
2 5

5 3 1 1 1

6
1 2
2 3
3 4
4 5
5 6

6 5 4 3 2 1

提示

样例解释

对于样例 1，构成的树如下图所示：

:::align{center}

:::

对于样例 2，构成的树如下图所示：

:::align{center}

:::

数据范围

• 对于 $30\%$ 的数据，满足 $n \le 100$。
• 对于 $60\%$ 的数据，满足 $n \le 1000$。
• 对于 $100\%$ 的数据，满足 $1 \le n \le 500,000$。保证输入的各条边能组成一棵含有 $n$ 个结点的树。