Descripción

Una empresa consta de $n$ miembros con identificadores de empleado $1, 2, \dots, n$. El miembro $1$ es el jefe, y cada uno de los demás miembros $i$ ($2 \le i \le n$) tiene un supervisor directo $f_i$ ($1 \le f_i < i$). La estructura de la empresa forma un árbol con raíz con el miembro $1$ en la raíz.

En esta empresa, el miembro $a$ conoce al miembro $b$ si y solo si se cumple al menos una de las siguientes condiciones:

• $a = b$.
• $b$ es un ancestro de $a$. En otras palabras, existe una secuencia $u_1, u_2, \dots, u_k$ ($2 \le k$) tal que $u_1 = a$, $u_k = b$, y $u_i = f_{u_{i-1}}$ para todo $2 \le i \le k$.
• $b$ es un hijo directo de $a$ ($b$ es un subordinado directo de $a$). En otras palabras, $f_b = a$.

Ten en cuenta que la relación de conocerse no es necesariamente simétrica; que $a$ conozca a $b$ no implica que $b$ conozca a $a$.

Ahora, los miembros están jugando a un juego. En cada ronda, un miembro específico $m$ actúa como el adivinador, y otro miembro $p$ es el objetivo. Se garantiza que $p$ es un miembro a quien $m$ no conoce.

Para identificar a $p$, $m$ hace una secuencia de preguntas. En cada pregunta, $m$ elige un identificador $x$ y pregunta: «¿Conoce $p$ al miembro $x$?». El miembro $p$ siempre responde con la verdad. Además, si $x = p$, $p$ revelará específicamente que es el miembro $x$, momento en el cual termina el juego.

Cada pregunta conlleva un costo de desplazamiento basado en el árbol de la empresa. Si la $i$-ésima pregunta se refiere al miembro $x_i$, el costo de esa pregunta es $dis(x_{i-1}, x_i)$, donde $dis(a, b)$ es el número de aristas en el único camino entre $a$ y $b$ en el árbol. Para la primera pregunta ($i = 1$), el costo es $dis(m, x_1)$.

El miembro $m$ es extremadamente inteligente y utiliza una estrategia óptima para minimizar el costo total requerido para garantizar la finalización del juego en el peor de los casos. Tu tarea es calcular este costo mínimo en el peor de los casos para cada posible adivinador $m \in \{1, 2, \dots, n\}$.

Si un miembro $m$ ya conoce a todos en la empresa, la respuesta para ese $m$ es $0$.

Entrada

La primera línea de la entrada contiene un entero $n$ ($1 \le n \le 10^5$), que representa el número total de miembros de la empresa.

La segunda línea contiene $n - 1$ enteros, que representan $f_2, f_3, \dots, f_n$. Se cumple que $1 \le f_i < i$.

Salida

Imprime una sola línea que contenga $n$ enteros, representando las respuestas para los casos en los que $m = 1, m = 2, \dots, m = n$. Los enteros deben estar separados por espacios.

Ejemplos

Entrada de ejemplo 1

3
1 1

Salida de ejemplo 1

0 2 2

Entrada de ejemplo 2

5
1 1 3 2

Salida de ejemplo 2

4 3 3 4 4

Entrada de ejemplo 3

6
1 1 2 2 3

Salida de ejemplo 3

4 3 5 4 4 6

Nota

Para explicar el caso de $m = 4$ en el ejemplo 3: Primero, como se muestra en el diagrama, el miembro $m$ no conoce a los miembros $\{3, 5, 6\}$. Una posible estrategia óptima es preguntar primero si el miembro $2$ es conocido por $p$, con un costo de $1$. De ser así, esto indica que $p = 5$, y el siguiente paso es preguntar por el miembro $5$ para terminar el juego, con un costo total de $2$. En caso contrario, se continúa preguntando si el miembro $3$ es conocido por $p$, con un costo de $2$. Si $p = 3$, el juego termina con un costo total de $3$. De lo contrario, esto indica que $p = 6$, y el siguiente paso cuesta $1$ para preguntar por el miembro $6$, terminando el juego con un costo total de $4$. Por lo tanto, esta estrategia requiere un costo en el peor de los casos de $4$. Se puede demostrar que ninguna otra estrategia puede reducir aún más el costo de consulta en el peor de los casos.