문제 설명

한 회사는 사원 번호가 $1, 2, \dots, n$인 $n$명의 구성원으로 이루어져 있습니다. 구성원 $1$은 사장이며, 다른 모든 구성원 $i$ ($2 \le i \le n$)에게는 직속 상사 $f_i$ ($1 \le f_i < i$)가 있습니다. 회사의 구조는 구성원 $1$을 루트로 하는 루트 있는 트리를 이룹니다.

이 회사에서 구성원 $a$가 구성원 $b$를 안다는 것은 다음 조건 중 적어도 하나를 만족하는 것과 동치입니다:

• $a = b$이다.
• $b$가 $a$의 조상이다. 즉, $u_1 = a$, $u_k = b$이고 모든 $2 \le i \le k$에 대해 $u_i = f_{u_{i-1}}$을 만족하는 수열 $u_1, u_2, \dots, u_k$ ($2 \le k$)가 존재한다.
• $b$가 $a$의 직접적인 자식이다($b$가 $a$의 직속 부하이다). 즉, $f_b = a$이다.

안다는 관계는 반드시 대칭적이지 않음에 유의하세요. 즉, $a$가 $b$를 안다고 해서 $b$가 $a$를 아는 것은 아닙니다.

이제 구성원들이 게임을 하고 있습니다. 각 라운드에서 특정 구성원 $m$은 질문자 역할을 하고, 다른 구성원 $p$는 타깃이 됩니다. $p$는 항상 $m$이 모르는 구성원임이 보장됩니다.

$p$가 누구인지 알아내기 위해 $m$은 일련의 질문을 던집니다. 각 질문에서 $m$은 번호 $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$)이 주어집니다.

두 번째 줄에는 $f_2, f_3, \dots, f_n$을 나타내는 $n - 1$개의 정수가 주어집니다. $1 \le f_i < i$를 만족합니다.

출력

$m = 1, m = 2, \dots, m = n$인 경우에 대한 정답을 나타내는 $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$로 게임을 끝낼 수 있습니다. 그렇지 않다면 계속해서 비용 $2$를 들여 $p$가 구성원 $3$을 아는지 묻습니다. 만약 $p = 3$이라면 총비용 $3$으로 게임이 끝납니다. 그렇지 않다면 $p = 6$임을 의미하므로, 다음 단계에서 비용 $1$을 들여 구성원 $6$에 대해 물어 총비용 $4$로 게임을 끝냅니다. 따라서 이 전략은 최악의 경우 $4$의 비용이 필요합니다. 다른 어떤 전략으로도 최악의 경우 질문 비용을 이보다 더 줄일 수 없음을 증명할 수 있습니다.