Description

A company consists of $n$ members with employee IDs $1, 2, \dots, n$. Member $1$ is the boss, and every other member $i$ ($2 \le i \le n$) has a direct supervisor $f_i$ ($1 \le f_i < i$). The company structure forms a rooted tree with member $1$ at the root.

In this company, member $a$ knows member $b$ if and only if at least one of the following conditions is satisfied:

• $a = b$.
• $b$ is an ancestor of $a$. In other words, there exists a sequence $u_1, u_2, \dots, u_k$ ($2 \le k$) such that $u_1 = a$, $u_k = b$, and $u_i = f_{u_{i-1}}$ for all $2 \le i \le k$.
• $b$ is a direct child of $a$ ($b$ is a direct subordinate of $a$). In other words, $f_b = a$.

Note that the acquaintance relationship is not necessarily symmetric; $a$ knowing $b$ does not imply that $b$ knows $a$.

Now, members are playing a game. In each round, a specific member $m$ acts as the guesser, and another member $p$ is the target. It is guaranteed that $p$ is a member whom $m$ does not know.

To identify $p$, $m$ asks a sequence of questions. For each question, $m$ chooses an ID $x$ and asks: "Does $p$ know member $x$?" Member $p$ always answers truthfully. Additionally, if $x = p$, $p$ will specifically reveal that they are member $x$, at which point the game ends.

Each question carries a travel cost based on the company tree. If the $i$-th question concerns member $x_i$, the cost of that question is $dis(x_{i-1}, x_i)$, where $dis(a, b)$ is the number of edges on the unique path between $a$ and $b$ in the tree. For the first question ($i = 1$), the cost is $dis(m, x_1)$.

Member $m$ is extremely clever and uses an optimal strategy to minimize the total cost required to guarantee the completion of the game in the worst-case scenario. Your task is to calculate this minimum worst-case cost for every possible guesser $m \in \{1, 2, \dots, n\}$.

If a member $m$ already knows everyone in the company, the answer for that $m$ is $0$.

Input

The first line of the input contains an integer $n$ ($1 \le n \le 10^5$), representing the total number of members in the company.

The second line contains $n - 1$ integers, representing $f_2, f_3, \dots, f_n$. It satisfies $1 \le f_i < i$.

Output

Output a single line containing $n$ integers, representing the answers for the cases where $m = 1, m = 2, \dots, m = n$. The integers should be separated by spaces.

Examples

Sample Input 1

3
1 1

Sample Output 1

0 2 2

Sample Input 2

5
1 1 3 2

Sample Output 2

4 3 3 4 4

Sample Input 3

6
1 1 2 2 3

Sample Output 3

4 3 5 4 4 6

Note

To explain the case of $m = 4$ in sample 3: First, as shown in the diagram, member $m$ does not know members $\{3, 5, 6\}$. One possible optimal strategy is to first ask if member $2$ is known by $p$, costing $1$. If so, it indicates that $p = 5$, and the next step is to ask about member $5$ to end the game, with a total cost of $2$. Otherwise, continue to ask if member $3$ is known by $p$, costing $2$. If $p = 3$, the game ends at a total cost of $3$. Otherwise, it indicates that $p = 6$, and the next step costs $1$ to ask about member $6$, ending the game with a total cost of $4$. Therefore, this strategy requires a worst-case cost of $4$. It can be proven that no other strategy can reduce the worst-case inquiry cost further.