問題文

ある会社には社員 ID $1, 2, \dots, n$ の $n$ 人のメンバーがいます。メンバー $1$ は社長であり、それ以外の各メンバー $i$（$2 \le i \le n$）には直属の上司 $f_i$（$1 \le f_i < i$）がいます。会社の組織構造はメンバー $1$ を根とする根付き木をなしています。

この会社では、以下の条件のうち少なくとも 1 つが満たされるとき、かつそのときに限り、メンバー $a$ はメンバー $b$ を知っていると定義されます：

• $a = b$ である。
• $b$ は $a$ の祖先である。言い換えると、ある列 $u_1, u_2, \dots, u_k$（$2 \le k$）が存在して、$u_1 = a$、$u_k = b$ であり、すべての $2 \le i \le k$ について $u_i = f_{u_{i-1}}$ を満たす。
• $b$ は $a$ の直接の子である（$b$ は $a$ の直属の部下である）。言い換えると、$f_b = a$ である。

この「知っている」という関係は必ずしも対称ではないことに注意してください。つまり、$a$ が $b$ を知っているからといって、$b$ が $a$ を知っているとは限りません。

今、メンバーたちはゲームをしています。各ラウンドでは、特定のメンバー $m$ が質問者となり、別のメンバー $p$ がターゲットとなります。$p$ は $m$ が知らないメンバーであることが保証されます。

$p$ を特定するために、$m$ は一連の質問を行います。各質問において、$m$ はある ID $x$ を選び、「$p$ はメンバー $x$ を知っていますか？」と尋ねます。メンバー $p$ は常に正直に答えます。さらに、$x = p$ の場合、$p$ は自分がメンバー $x$ であることを特別に明かし、その時点でゲームは終了します。

各質問には、会社の木構造に基づいた移動コストがかかります。$i$ 番目の質問がメンバー $x_i$ に関するものであるとき、その質問のコストは $dis(x_{i-1}, x_i)$ です。ここで $dis(a, b)$ は木における $a$ と $b$ の間の唯一のパスに含まれる辺の本数を表します。最初の質問（$i = 1$）のコストは $dis(m, x_1)$ です。

メンバー $m$ は非常に賢く、最悪ケースにおいてゲームを確実に終了させるために必要な総コストを最小化する最適戦略をとります。あなたの仕事は、すべての可能な質問者 $m \in \{1, 2, \dots, n\}$ について、この最悪ケースにおける最小コストを計算することです。

もしメンバー $m$ が社内の全員をすでに知っている場合、その $m$ に対する答えは $0$ です。

入力

入力の 1 行目には、会社のメンバーの総数を表す整数 $n$（$1 \le n \le 10^5$）が与えられます。

2 行目には、$f_2, f_3, \dots, f_n$ を表す $n - 1$ 個の整数が与えられます。$1 \le f_i < i$ を満たします。

出力

$m = 1, m = 2, \dots, m = n$ の場合の答えを表す $n$ 個の整数を空白区切りで 1 行に出力してください。

入力例・出力例

入力例 1

3
1 1

出力例 1

0 2 2

入力例 2

5
1 1 3 2

出力例 2

4 3 3 4 4

入力例 3

6
1 1 2 2 3

出力例 3

4 3 5 4 4 6

注記

入力例 3 における $m = 4$ の場合を説明します。まず、図に示されている通り、メンバー $m$ はメンバー $\{3, 5, 6\}$ を知りません。考えられる最適戦略の 1 つは、最初に $p$ がメンバー $2$ を知っているかをコスト $1$ で尋ねることです。もし知っていれば $p = 5$ であることがわかるため、次にメンバー $5$ について尋ねることでゲームが終了し、総コストは $2$ となります。そうでなければ、続いて $p$ がメンバー $3$ を知っているかをコスト $2$ で尋ねます。もし $p = 3$ であれば総コスト $3$ でゲームが終了します。そうでなければ $p = 6$ であることがわかるため、次にコスト $1$ をかけてメンバー $6$ について尋ねることで、総コスト $4$ でゲームが終了します。したがって、この戦略における最悪ケースのコストは $4$ です。これ以上に最悪ケースの質問コストを減らせる戦略は存在しないことが証明できます。