題目描述

一家公司由 $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$。可以證明，沒有其他策略可以進一步降低最壞情況下的詢問代價。