題目描述

一間公司由 $n$ 名成員組成，員工 ID 分別係 $1, 2, \dots, n$。成員 $1$ 係老闆，其他每位成員 $i$（$2 \le i \le n$）都有一位直屬上司 $f_i$（$1 \le f_i < i$）。公司架構形成一棵以成員 $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$。

輸入格式

輸入嘅第一行包含一個整數 $n$（$1 \le n \le 10^5$），代表公司入面嘅成員總數。

第二行包含 $n - 1$ 個整數，代表 $f_2, f_3, \dots, f_n$。滿足 $1 \le f_i < i$。

輸出格式

輸出單行包含 $n$ 個整數，代表 $m = 1, m = 2, \dots, m = n$ 時嘅答案。整數之間用空格隔開。

範例

範例輸入 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\}$。一種可能嘅最優策略係先問 $p$ 識唔識得成員 $2$，代價為 $1$。如果識得，就表示 $p = 5$，下一步問成員 $5$ 結束遊戲，總代價為 $2$。否則，繼續問 $p$ 識唔識得成員 $3$，代價為 $2$。如果 $p = 3$，遊戲結束，總代價為 $3$。否則，表示 $p = 6$，下一步用 $1$ 嘅代價問成員 $6$，遊戲結束，總代價為 $4$。因此，呢個策略喺最壞情況下嘅代價為 $4$。可以證明冇其他策略可以進一步降低最壞情況下嘅詢問代價。