Description

Une entreprise est composée de $n$ membres ayant les identifiants d'employé $1, 2, \dots, n$. Le membre $1$ est le patron, et chaque autre membre $i$ ($2 \le i \le n$) a un superviseur direct $f_i$ ($1 \le f_i < i$). La structure de l'entreprise forme un arbre enraciné dont la racine est le membre $1$.

Dans cette entreprise, le membre $a$ connaît le membre $b$ si et seulement si au moins l'une des conditions suivantes est satisfaite :

• $a = b$.
• $b$ est un ancêtre de $a$. En d'autres termes, il existe une suite $u_1, u_2, \dots, u_k$ ($2 \le k$) telle que $u_1 = a$, $u_k = b$, et $u_i = f_{u_{i-1}}$ pour tout $2 \le i \le k$.
• $b$ est un enfant direct de $a$ ($b$ est un subordonné direct de $a$). En d'autres termes, $f_b = a$.

Notez que la relation de connaissance n'est pas nécessairement symétrique ; le fait que $a$ connaisse $b$ n'implique pas que $b$ connaisse $a$.

Maintenant, les membres jouent à un jeu. À chaque manche, un membre spécifique $m$ agit comme le devineur, et un autre membre $p$ est la cible. Il est garanti que $p$ est un membre que $m$ ne connaît pas.

Pour identifier $p$, $m$ pose une séquence de questions. Pour chaque question, $m$ choisit un identifiant $x$ et demande : « Est-ce que $p$ connaît le membre $x$ ? » Le membre $p$ répond toujours honnêtement. De plus, si $x = p$, $p$ révélera spécifiquement qu'il est le membre $x$, moment auquel le jeu se termine.

Chaque question entraîne un coût de déplacement basé sur l'arbre de l'entreprise. Si la $i$-ème question concerne le membre $x_i$, le coût de cette question est $dis(x_{i-1}, x_i)$, où $dis(a, b)$ est le nombre d'arêtes sur l'unique chemin entre $a$ et $b$ dans l'arbre. Pour la première question ($i = 1$), le coût est $dis(m, x_1)$.

Le membre $m$ est extrêmement intelligent et utilise une stratégie optimale pour minimiser le coût total requis afin de garantir la fin du jeu dans le pire des cas. Votre tâche consiste à calculer ce coût minimal dans le pire des cas pour chaque devineur possible $m \in \{1, 2, \dots, n\}$.

Si un membre $m$ connaît déjà tout le monde dans l'entreprise, la réponse pour ce $m$ est $0$.

Entrée

La première ligne de l'entrée contient un entier $n$ ($1 \le n \le 10^5$), représentant le nombre total de membres dans l'entreprise.

La deuxième ligne contient $n - 1$ entiers, représentant $f_2, f_3, \dots, f_n$. Ils vérifient $1 \le f_i < i$.

Sortie

Affichez une seule ligne contenant $n$ entiers, représentant les réponses pour les cas où $m = 1, m = 2, \dots, m = n$. Les entiers doivent être séparés par des espaces.

Exemples

Entrée d'exemple 1

3
1 1

Sortie d'exemple 1

0 2 2

Entrée d'exemple 2

5
1 1 3 2

Sortie d'exemple 2

4 3 3 4 4

Entrée d'exemple 3

6
1 1 2 2 3

Sortie d'exemple 3

4 3 5 4 4 6

Note

Pour expliquer le cas $m = 4$ dans l'exemple 3 : Tout d'abord, comme illustré sur le schéma, le membre $m$ ne connaît pas les membres $\{3, 5, 6\}$. Une stratégie optimale possible consiste à demander d'abord si le membre $2$ est connu de $p$, ce qui coûte $1$. Si c'est le cas, cela indique que $p = 5$, et l'étape suivante consiste à poser la question sur le membre $5$ pour terminer le jeu, avec un coût total de $2$. Sinon, on continue en demandant si le membre $3$ est connu de $p$, ce qui coûte $2$. Si $p = 3$, le jeu se termine avec un coût total de $3$. Sinon, cela indique que $p = 6$, et l'étape suivante coûte $1$ pour interroger le membre $6$, terminant le jeu avec un coût total de $4$. Par conséquent, cette stratégie nécessite un coût de $4$ dans le pire des cas. On peut prouver qu'aucune autre stratégie ne peut réduire davantage le coût d'interrogation dans le pire des cas.