说明

对于 $r = 1, 2, \ldots, N$，分别解决以下问题。

有 $N$ 个岛屿，通过 $N - 1$ 座桥梁，可以在任意两个岛屿之间通行。

当有消息需要通知所有岛屿时，传单会以一种有些特别的方式分发。首先，在岛屿 $r$ 上恰好生成一份传单。之后，重复以下操作：

选择一份传单，设 $u$ 为当前持有它的岛屿。将这份传单复制一次，然后将原件和副本（总共两份传单）通过桥梁送到与 $u$ 相连的岛屿。这两份传单可以送到同一个岛屿，也可以送到两个不同的岛屿。

确定在满足每个岛屿都至少有一份传单的前提下，所需的最少操作次数。

输入格式

输入包含一个单独的测试用例，格式如下：

$$\begin{aligned} & N \\ & u_1 \ v_1 \\ & \vdots \\ & u_{N-1} \ v_{N-1} \end{aligned}$$

第一行包含一个整数 $N$（$2 \leq N \leq 300\,000$），表示岛屿的数量。

接下来的 $N - 1$ 行，每行包含两个整数 $u_i, v_i$（$1 \leq u_i, v_i \leq N$，$u_i \neq v_i$），表示第 $i$ 座桥梁连接岛屿 $u_i$ 和岛屿 $v_i$。

保证可以通过桥梁在任意两个岛屿之间通行。

输出格式

输出 $N$ 个整数，以空格分隔。第 $i$ 个整数应包含当 $r = i$ 时的最少操作次数。

3
1 2
2 3

2 3 2

5
3 1
2 3
3 5
3 4

5 5 5 5 5

提示

翻译由 DeepSeek V3.2 完成