Beschreibung

Ein Unternehmen besteht aus $n$ Mitgliedern mit den Mitarbeiter-IDs $1, 2, \dots, n$. Mitglied $1$ ist der Chef, und jedes andere Mitglied $i$ ($2 \le i \le n$) hat einen direkten Vorgesetzten $f_i$ ($1 \le f_i < i$). Die Unternehmensstruktur bildet einen Wurzelbaum mit Mitglied $1$ als Wurzel.

In diesem Unternehmen kennt Mitglied $a$ Mitglied $b$ genau dann, wenn mindestens eine der folgenden Bedingungen erfüllt ist:

• $a = b$.
• $b$ ist ein Vorfahre von $a$. Mit anderen Worten, es existiert eine Folge $u_1, u_2, \dots, u_k$ ($2 \le k$), sodass $u_1 = a$, $u_k = b$ und $u_i = f_{u_{i-1}}$ für alle $2 \le i \le k$ gilt.
• $b$ ist ein direktes Kind von $a$ ($b$ ist ein direkter Untergebener von $a$). Mit anderen Worten, $f_b = a$.

Beachte, dass die Bekanntschaftsbeziehung nicht unbedingt symmetrisch ist; dass $a$ Mitglied $b$ kennt, bedeutet nicht zwangsläufig, dass $b$ auch $a$ kennt.

Nun spielen die Mitglieder ein Spiel. In jeder Runde agiert ein bestimmtes Mitglied $m$ als Ratender, und ein anderes Mitglied $p$ ist das Ziel. Es wird garantiert, dass $p$ ein Mitglied ist, das $m$ nicht kennt.

Um $p$ zu identifizieren, stellt $m$ eine Reihe von Fragen. Bei jeder Frage wählt $m$ eine ID $x$ und fragt: „Kennt $p$ das Mitglied $x$?“ Mitglied $p$ antwortet immer wahrheitsgemäß. Wenn außerdem $x = p$ gilt, gibt $p$ ausdrücklich preis, dass es selbst Mitglied $x$ ist, woraufhin das Spiel endet.

Jede Frage verursacht Reisekosten basierend auf dem Unternehmensbaum. Wenn sich die $i$-te Frage auf Mitglied $x_i$ bezieht, betragen die Kosten dieser Frage $dis(x_{i-1}, x_i)$, wobei $dis(a, b)$ die Anzahl der Kanten auf dem eindeutigen Pfad zwischen $a$ und $b$ im Baum ist. Für die erste Frage ($i = 1$) betragen die Kosten $dis(m, x_1)$.

Mitglied $m$ ist äußerst klug und verwendet eine optimale Strategie, um die Gesamtkosten zu minimieren, die erforderlich sind, um den Abschluss des Spiels im schlimmsten Fall (Worst Case) zu garantieren. Deine Aufgabe ist es, diese minimalen Worst-Case-Kosten für jeden möglichen Ratenden $m \in \{1, 2, \dots, n\}$ zu berechnen.

Wenn ein Mitglied $m$ bereits jeden im Unternehmen kennt, ist die Antwort für dieses $m$ gleich $0$.

Eingabe

Die erste Zeile der Eingabe enthält eine ganze Zahl $n$ ($1 \le n \le 10^5$), die die Gesamtzahl der Mitglieder im Unternehmen darstellt.

Die zweite Zeile enthält $n - 1$ ganze Zahlen, die $f_2, f_3, \dots, f_n$ darstellen. Es gilt $1 \le f_i < i$.

Ausgabe

Gib eine einzige Zeile mit $n$ ganzen Zahlen aus, die die Antworten für die Fälle $m = 1, m = 2, \dots, m = n$ darstellen. Die ganzen Zahlen sollten durch Leerzeichen getrennt sein.

Beispiele

Beispieleingabe 1

3
1 1

Beispielausgabe 1

0 2 2

Beispieleingabe 2

5
1 1 3 2

Beispielausgabe 2

4 3 3 4 4

Beispieleingabe 3

6
1 1 2 2 3

Beispielausgabe 3

4 3 5 4 4 6

Hinweis

Zur Erklärung des Falls $m = 4$ in Beispiel 3: Zunächst kennt Mitglied $m$, wie im Diagramm gezeigt, die Mitglieder $\{3, 5, 6\}$ nicht. Eine mögliche optimale Strategie besteht darin, zuerst zu fragen, ob Mitglied $2$ von $p$ gekannt wird, was $1$ kostet. Falls ja, bedeutet dies $p = 5$, und der nächste Schritt besteht darin, nach Mitglied $5$ zu fragen, um das Spiel mit Gesamtkosten von $2$ zu beenden. Andernfalls fragt man weiter, ob Mitglied $3$ von $p$ gekannt wird, was $2$ kostet. Wenn $p = 3$ ist, endet das Spiel mit Gesamtkosten von $3$. Andernfalls bedeutet dies $p = 6$, und der nächste Schritt kostet $1$, um nach Mitglied $6$ zu fragen, womit das Spiel mit Gesamtkosten von $4$ endet. Daher erfordert diese Strategie im schlimmsten Fall Kosten von $4$. Es lässt sich beweisen, dass keine andere Strategie die Fragekosten im schlimmsten Fall weiter senken kann.