Opis problemu

Firma składa się z $n$ członków o identyfikatorach pracowników $1, 2, \dots, n$. Członek $1$ jest szefem, a każdy inny członek $i$ ($2 \le i \le n$) ma bezpośredniego przełożonego $f_i$ ($1 \le f_i < i$). Struktura firmy tworzy drzewo ukorzenione z członkiem $1$ w korzeniu.

W tej firmie członek $a$ zna członka $b$ wtedy i tylko wtedy, gdy spełniony jest co najmniej jeden z poniższych warunków:

• $a = b$.
• $b$ jest przodkiem $a$. Innymi słowy, istnieje ciąg $u_1, u_2, \dots, u_k$ ($2 \le k$) taki, że $u_1 = a$, $u_k = b$ oraz $u_i = f_{u_{i-1}}$ dla wszystkich $2 \le i \le k$.
• $b$ jest bezpośrednim dzieckiem $a$ ($b$ jest bezpośrednim podwładnym $a$). Innymi słowy, $f_b = a$.

Zauważ, że relacja znajomości nie musi być symetryczna; to, że $a$ zna $b$, nie oznacza, że $b$ zna $a$.

Teraz członkowie grają w grę. W każdej rundzie określony członek $m$ pełni rolę zgadującego, a inny członek $p$ jest celem. Gwarantuje się, że $p$ jest członkiem, którego $m$ nie zna.

Aby zidentyfikować $p$, $m$ zadaje ciąg pytań. W każdym pytaniu $m$ wybiera pewien identyfikator $x$ i pyta: „Czy $p$ zna członka $x$?”. Członek $p$ zawsze odpowiada zgodnie z prawdą. Ponadto, jeśli $x = p$, $p$ wyraźnie ujawni, że jest członkiem $x$, i w tym momencie gra się kończy.

Każde pytanie wiąże się z kosztem podróży po drzewie firmy. Jeśli $i$-te pytanie dotyczy członka $x_i$, koszt tego pytania wynosi $dis(x_{i-1}, x_i)$, gdzie $dis(a, b)$ jest liczbą krawędzi na jednoznacznej ścieżce między $a$ i $b$ w drzewie. Dla pierwszego pytania ($i = 1$) koszt wynosi $dis(m, x_1)$.

Członek $m$ jest niezwykle bystry i stosuje optymalną strategię, aby zminimalizować łączny koszt wymagany do zagwarantowania ukończenia gry w najgorszym przypadku. Twoim zadaniem jest obliczenie tego minimalnego kosztu w najgorszym przypadku dla każdego możliwego zgadującego $m \in \{1, 2, \dots, n\}$.

Jeśli członek $m$ zna już wszystkich w firmie, odpowiedzią dla tego $m$ jest $0$.

Wejście

Pierwszy wiersz wejścia zawiera liczbę całkowitą $n$ ($1 \le n \le 10^5$), reprezentującą łączną liczbę członków w firmie.

Drugi wiersz zawiera $n - 1$ liczb całkowitych, reprezentujących $f_2, f_3, \dots, f_n$. Spełniony jest warunek $1 \le f_i < i$.

Wyjście

Wypisz jeden wiersz zawierający $n$ liczb całkowitych, reprezentujących odpowiedzi dla przypadków $m = 1, m = 2, \dots, m = n$. Liczby całkowite powinny być oddzielone spacjami.

Przykłady

Przykładowe wejście 1

3
1 1

Przykładowe wyjście 1

0 2 2

Przykładowe wejście 2

5
1 1 3 2

Przykładowe wyjście 2

4 3 3 4 4

Przykładowe wejście 3

6
1 1 2 2 3

Przykładowe wyjście 3

4 3 5 4 4 6

Uwaga

Aby wyjaśnić przypadek $m = 4$ w przykładzie 3: Po pierwsze, jak pokazano na schemacie, członek $m$ nie zna członków $\{3, 5, 6\}$. Jedną z możliwych optymalnych strategii jest najpierw zapytanie, czy członek $2$ jest znany przez $p$, co kosztuje $1$. Jeśli tak, oznacza to, że $p = 5$, a następnym krokiem jest zapytanie o członka $5$, aby zakończyć grę przy łącznym koszcie $2$. W przeciwnym razie kontynuujemy, pytając, czy członek $3$ jest znany przez $p$, co kosztuje $2$. Jeśli $p = 3$, gra kończy się przy łącznym koszcie $3$. W przeciwnym razie oznacza to, że $p = 6$, a następny krok kosztuje $1$, aby zapytać o członka $6$, co kończy grę przy łącznym koszcie $4$. Zatem strategia ta wymaga w najgorszym przypadku kosztu $4$. Można udowodnić, że żadna inna strategia nie może jeszcze bardziej zmniejszyć kosztu zapytań w najgorszym przypadku.