Deskripsi

Sebuah perusahaan terdiri dari $n$ anggota dengan ID karyawan $1, 2, \dots, n$. Anggota $1$ adalah bos, dan setiap anggota lainnya $i$ ($2 \le i \le n$) memiliki atasan langsung $f_i$ ($1 \le f_i < i$). Struktur perusahaan membentuk pohon berakar dengan anggota $1$ sebagai akarnya.

Di perusahaan ini, anggota $a$ mengenal anggota $b$ jika dan hanya jika setidaknya satu dari kondisi berikut terpenuhi:

• $a = b$.
• $b$ adalah leluhur dari $a$. Dengan kata lain, terdapat barisan $u_1, u_2, \dots, u_k$ ($2 \le k$) sedemikian sehingga $u_1 = a$, $u_k = b$, dan $u_i = f_{u_{i-1}}$ untuk semua $2 \le i \le k$.
• $b$ adalah anak langsung dari $a$ ($b$ adalah bawahan langsung dari $a$). Dengan kata lain, $f_b = a$.

Perhatikan bahwa hubungan perkenalan ini tidak harus simetris; $a$ mengenal $b$ tidak berarti $b$ mengenal $a$.

Sekarang, para anggota sedang memainkan sebuah permainan. Di setiap ronde, seorang anggota tertentu $m$ bertindak sebagai penebak, dan anggota lainnya $p$ adalah target. Dijamin bahwa $p$ adalah anggota yang tidak dikenal oleh $m$.

Untuk mengidentifikasi $p$, $m$ mengajukan serangkaian pertanyaan. Untuk setiap pertanyaan, $m$ memilih sebuah ID $x$ dan bertanya: "Apakah $p$ mengenal anggota $x$?" Anggota $p$ selalu menjawab dengan jujur. Selain itu, jika $x = p$, $p$ akan secara khusus mengungkapkan bahwa dirinya adalah anggota $x$, dan pada saat itu permainan berakhir.

Setiap pertanyaan memiliki biaya perjalanan berdasarkan pohon perusahaan. Jika pertanyaan ke-$i$ berkaitan dengan anggota $x_i$, biaya dari pertanyaan tersebut adalah $dis(x_{i-1}, x_i)$, dengan $dis(a, b)$ adalah jumlah sisi pada jalur unik antara $a$ dan $b$ di dalam pohon. Untuk pertanyaan pertama ($i = 1$), biayanya adalah $dis(m, x_1)$.

Anggota $m$ sangat cerdas dan menggunakan strategi optimal untuk meminimalkan total biaya yang diperlukan guna menjamin selesainya permainan dalam skenario kasus terburuk. Tugas Anda adalah menghitung biaya kasus terburuk minimum ini untuk setiap kemungkinan penebak $m \in \{1, 2, \dots, n\}$.

Jika seorang anggota $m$ sudah mengenal semua orang di perusahaan, jawaban untuk $m$ tersebut adalah $0$.

Masukan

Baris pertama masukan berisi sebuah bilangan bulat $n$ ($1 \le n \le 10^5$), yang menyatakan jumlah total anggota di perusahaan.

Baris kedua berisi $n - 1$ bilangan bulat, yang menyatakan $f_2, f_3, \dots, f_n$. Memenuhi $1 \le f_i < i$.

Keluaran

Keluarkan satu baris yang berisi $n$ bilangan bulat, yang menyatakan jawaban untuk kasus-kasus di mana $m = 1, m = 2, \dots, m = n$. Bilangan-bilangan bulat tersebut harus dipisahkan dengan spasi.

Contoh

Contoh Masukan 1

3
1 1

Contoh Keluaran 1

0 2 2

Contoh Masukan 2

5
1 1 3 2

Contoh Keluaran 2

4 3 3 4 4

Contoh Masukan 3

6
1 1 2 2 3

Contoh Keluaran 3

4 3 5 4 4 6

Catatan

Untuk menjelaskan kasus $m = 4$ pada contoh 3: Pertama, seperti yang ditunjukkan pada diagram, anggota $m$ tidak mengenal anggota $\{3, 5, 6\}$. Salah satu strategi optimal yang mungkin adalah pertama-tama menanyakan apakah anggota $2$ dikenal oleh $p$, dengan biaya $1$. Jika ya, itu menunjukkan bahwa $p = 5$, dan langkah selanjutnya adalah menanyakan tentang anggota $5$ untuk mengakhiri permainan, dengan total biaya $2$. Jika tidak, lanjutkan menanyakan apakah anggota $3$ dikenal oleh $p$, dengan biaya $2$. Jika $p = 3$, permainan berakhir dengan total biaya $3$. Jika tidak, itu menunjukkan bahwa $p = 6$, dan langkah selanjutnya memakan biaya $1$ untuk menanyakan tentang anggota $6$, mengakhiri permainan dengan total biaya $4$. Oleh karena itu, strategi ini memerlukan biaya kasus terburuk sebesar $4$. Dapat dibuktikan bahwa tidak ada strategi lain yang dapat mengurangi biaya pertanyaan kasus terburuk lebih lanjut.