問題文

高速な言語の使用を推奨します。 Writer 解は約 1200 ms (C++) です。

ワンコ王国には $N$ 個の都市と、 $2$ 都市間を結ぶ $N - 1$ 本の道路があります。$i$ 番目の道路は都市 $X_i, Y_i$ を結んでいます。また全ての都市の組について、互いの間を道路の移動のみで行き来することができます。つまり、ワンコ王国の都市と道路をグラフとみるとそれは木グラフです。

ポチはスタンプラリーをしています。スタンプラリーは都市 $1$ で始まり、都市 $1, 2, 3, \cdots ,N$ の順に、その都市を訪れてスタンプを集める必要があります。ポチは道路の端点と逆側の端点の移動に $1$ 秒かかります。

ポチはスタンプラリーを手短に済ませたいので、ワープ装置を $1$ つ持ち込むことにしました。ポチは、ある $k \ (1 \leq k \leq N)$ を $1$ つ選び、都市 $k$ でスタンプを押したタイミングでそこにワープ装置を設置します。ある都市にワープ装置が設置されている場合、任意の都市からその都市に $1$ 秒で移動することができます。

ポチが有意義にワープ装置を使うために、 $k = 1, 2, \cdots , N$ それぞれについて、ポチが適切に移動することで実現できる、スタンプラリーを完了する時間の最小値を求めてください。スタンプを押すのにかかる時間は無視するものとします。

入力

$N$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_{N-1}$ $Y_{N-1}$

• 入力はすべて整数で与えられる。
• 入力で与えられるグラフは木グラフである。
• $2 \leq N \leq 10^5$
• $1 \leq X_i, Y_i \leq N$

出力

$N$ 行出力せよ。$i \ (1 \leq i \leq N)$ 行目には、 $k=i$ としたときの答えを、単位を秒として出力せよ。

サンプル

6
2 1
6 4
2 5
1 6
2 3

10
11
12
12
13
13

7
1 7
7 2
2 6
6 3
3 4
4 5

11
10
10
11
11
11
11

10
10 7
3 7
8 4
8 6
4 3
1 5
1 4
2 10
4 9

28
25
25
25
28
27
26
28
28
28