תיאור הבעיה

חברה מורכבת מ-$n$ חברים עם מזהי עובדים $1, 2, \dots, n$. חבר $1$ הוא הבוס, ולכל חבר אחר $i$ ($2 \le i \le n$) יש מנהל ישיר $f_i$ ($1 \le f_i < i$). מבנה החברה יוצר עץ מכוון שורש שבו חבר $1$ נמצא בשורש.

בחברה זו, חבר $a$ מכיר את חבר $b$ אם ורק אם מתקיים לפחות אחד מהתנאים הבאים:

• $a = b$.
• $b$ הוא אב קדמון של $a$. במילים אחרות, קיימת סדרה $u_1, u_2, \dots, u_k$ ($2 \le k$) כך ש-$u_1 = a$, $u_k = b$, ו-$u_i = f_{u_{i-1}}$ לכל $2 \le i \le k$.
• $b$ הוא ילד ישיר של $a$ ($b$ הוא כפוף ישיר של $a$). במילים אחרות, $f_b = a$.

שימו לב שיחס ההיכרות אינו בהכרח סימטרי; העובדה ש-$a$ מכיר את $b$ אינה גוררת ש-$b$ מכיר את $a$.

כעת, החברים משחקים במשחק. בכל סיבוב, חבר מסוים $m$ משמש כמנחש, וחבר אחר $p$ הוא המטרה. מובטח כי $p$ הוא חבר ש-$m$ אינו מכיר.

כדי לזהות את $p$, $m$ שואל סדרה של שאלות. עבור כל שאלה, $m$ בוחר מזהה $x$ ושואל: "האם $p$ מכיר את חבר $x$?" חבר $p$ תמיד עונה בכנות. בנוסף, אם $x = p$, $p$ יחשוף במפורש שהוא חבר $x$, ובנקודה זו המשחק מסתיים.

לכל שאלה יש עלות מעבר המבוססת על עץ החברה. אם השאלה ה-$i$ עוסקת בחבר $x_i$, עלות השאלה היא $dis(x_{i-1}, x_i)$, כאשר $dis(a, b)$ הוא מספר הקשתות במסלול היחיד בין $a$ ל-$b$ בעץ. עבור השאלה הראשונה ($i = 1$), העלות היא $dis(m, x_1)$.

חבר $m$ הוא חכם ביותר ומשתמש באסטרטגיה אופטימלית כדי למזער את העלות הכוללת הנדרשת להבטחת סיום המשחק בתרחיש הגרוע ביותר. משימתך היא לחשב את העלות המינימלית הזו במקרה הגרוע ביותר עבור כל מנחש אפשרי $m \in \{1, 2, \dots, n\}$.

אם חבר $m$ כבר מכיר את כולם בחברה, התשובה עבור אותו $m$ היא $0$.

קלט

השורה הראשונה של הקלט מכילה מספר שלם $n$ ($1 \le n \le 10^5$), המייצג את המספר הכולל של החברים בחברה.

השורה השנייה מכילה $n - 1$ מספרים שלמים, המייצגים את $f_2, f_3, \dots, f_n$. מתקיים $1 \le f_i < i$.

פלט

הדפס שורה בודדת המכילה $n$ מספרים שלמים, המייצגים את התשובות עבור המקרים שבהם $m = 1, m = 2, \dots, m = n$. המספרים השלמים צריכים להיות מופרדים ברווחים.

דוגמאות

קלט לדוגמה 1

3
1 1

פלט לדוגמה 1

0 2 2

קלט לדוגמה 2

5
1 1 3 2

פלט לדוגמה 2

4 3 3 4 4

קלט לדוגמה 3

6
1 1 2 2 3

פלט לדוגמה 3

4 3 5 4 4 6

הערה

כדי להסביר את המקרה של $m = 4$ בדוגמה 3: ראשית, כפי שמוצג בתרשים, חבר $m$ אינו מכיר את החברים $\{3, 5, 6\}$. אסטרטגיה אופטימלית אפשרית אחת היא לשאול תחילה אם חבר $2$ מוכר ל-$p$, בעלות של $1$. אם כן, הדבר מעיד על כך ש-$p = 5$, והצעד הבא הוא לשאול על חבר $5$ כדי לסיים את המשחק, בעלות כוללת של $2$. אחרת, ממשיכים ושואלים אם חבר $3$ מוכר ל-$p$, בעלות של $2$. אם $p = 3$, המשחק מסתיים בעלות כוללת של $3$. אחרת, הדבר מעיד על כך ש-$p = 6$, והצעד הבא עולה $1$ כדי לשאול על חבר $6$, ומסיים את המשחק בעלות כוללת של $4$. לכן, אסטרטגיה זו דורשת עלות של $4$ במקרה הגרוע ביותר. ניתן להוכיח שאף אסטרטגיה אחרת אינה יכולה להפחית עוד יותר את עלות השאילתות במקרה הגרוע ביותר.