Descrizione

Un'azienda è composta da $n$ membri con ID dipendente $1, 2, \dots, n$. Il membro $1$ è il capo, e ogni altro membro $i$ ($2 \le i \le n$) ha un supervisore diretto $f_i$ ($1 \le f_i < i$). La struttura aziendale forma un albero radicato con il membro $1$ alla radice.

In questa azienda, il membro $a$ conosce il membro $b$ se e solo se è soddisfatta almeno una delle seguenti condizioni:

• $a = b$.
• $b$ è un antenato di $a$. In altre parole, esiste una sequenza $u_1, u_2, \dots, u_k$ ($2 \le k$) tale che $u_1 = a$, $u_k = b$, e $u_i = f_{u_{i-1}}$ per tutti i $2 \le i \le k$.
• $b$ è un figlio diretto di $a$ ($b$ è un subordinato diretto di $a$). In altre parole, $f_b = a$.

Si noti che la relazione di conoscenza non è necessariamente simmetrica; il fatto che $a$ conosca $b$ non implica che $b$ conosca $a$.

Ora, i membri stanno facendo un gioco. In ogni turno, uno specifico membro $m$ agisce come indovino, e un altro membro $p$ è il bersaglio. È garantito che $p$ sia un membro che $m$ non conosce.

Per identificare $p$, $m$ pone una sequenza di domande. Per ogni domanda, $m$ sceglie un ID $x$ e chiede: «$p$ conosce il membro $x$?» Il membro $p$ risponde sempre sinceramente. Inoltre, se $x = p$, $p$ rivelerà specificamente di essere il membro $x$, dopodiché il gioco termina.

Ogni domanda comporta un costo di spostamento basato sull'albero aziendale. Se la $i$-esima domanda riguarda il membro $x_i$, il costo di tale domanda è $dis(x_{i-1}, x_i)$, dove $dis(a, b)$ è il numero di archi sull'unico cammino tra $a$ e $b$ nell'albero. Per la prima domanda ($i = 1$), il costo è $dis(m, x_1)$.

Il membro $m$ è estremamente intelligente e utilizza una strategia ottimale per ridurre al minimo il costo totale richiesto per garantire il completamento del gioco nello scenario del caso peggiore. Il tuo compito è calcolare questo costo minimo nel caso peggiore per ogni possibile indovino $m \in \{1, 2, \dots, n\}$.

Se un membro $m$ conosce già tutti in azienda, la risposta per quel $m$ è $0$.

Input

La prima riga dell'input contiene un intero $n$ ($1 \le n \le 10^5$), che rappresenta il numero totale di membri nell'azienda.

La seconda riga contiene $n - 1$ interi, che rappresentano $f_2, f_3, \dots, f_n$. Vale $1 \le f_i < i$.

Output

Stampa una singola riga contenente $n$ interi, che rappresentano le risposte per i casi in cui $m = 1, m = 2, \dots, m = n$. Gli interi devono essere separati da spazi.

Esempi

Input di esempio 1

3
1 1

Output di esempio 1

0 2 2

Input di esempio 2

5
1 1 3 2

Output di esempio 2

4 3 3 4 4

Input di esempio 3

6
1 1 2 2 3

Output di esempio 3

4 3 5 4 4 6

Nota

Per spiegare il caso di $m = 4$ nell'esempio 3: Innanzitutto, come mostrato nel diagramma, il membro $m$ non conosce i membri $\{3, 5, 6\}$. Una possibile strategia ottimale consiste nel chiedere per prima cosa se il membro $2$ è conosciuto da $p$, con un costo pari a $1$. In caso affermativo, ciò indica che $p = 5$, e il passo successivo consiste nel chiedere del membro $5$ per terminare il gioco, con un costo totale di $2$. Altrimenti, si continua chiedendo se il membro $3$ è conosciuto da $p$, con un costo di $2$. Se $p = 3$, il gioco termina con un costo totale di $3$. Altrimenti, ciò indica che $p = 6$, e il passo successivo costa $1$ per chiedere del membro $6$, terminando il gioco con un costo totale di $4$. Pertanto, questa strategia richiede un costo nel caso peggiore pari a $4$. Si può dimostrare che nessun'altra strategia può ridurre ulteriormente il costo di interrogazione nel caso peggiore.