题目描述

Solve the following problem for $r = 1, 2, \ldots, N$.

There are $N$ islands, and with $N - 1$ bridges it is possible to travel between any two islands.

When there is an announcement to be made to all islands, flyers are distributed in a somewhat unusual way. First, exactly one flyer is created on island $r$. After that, the following operation is repeated:

Choose one flyer, and let $u$ be the island that currently has it. Duplicate the flyer once, and deliver the original and the duplicate (exactly two flyers in total) to islands connected to $u$ by a bridge. These two flyers may both be delivered to the same island or to two different islands.

Determine the minimum number of operations required until every island has at least one flyer.

输入格式

The input consists of a single test case in the following format.

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

The first line contains an integer $N$ ($2 \leq N \leq 300\,000$), representing the number of islands.

The following $N - 1$ lines each contain integers $u_i, v_i$ ($1 \leq u_i, v_i \leq N$, $u_i \neq v_i$), representing that the $i$-th bridge connects island $u_i$ and island $v_i$.

It is guaranteed that one can travel between any two islands using bridges.

输出格式

Output $N$ integers separated by spaces. The $i$-th integer should contain the minimum number of operations when $r = i$.

3
1 2
2 3

2 3 2

5
3 1
2 3
3 5
3 4

5 5 5 5 5