זוהי בעיה רב-שלבית (multi-pass problem).

בארכיונים הדיגיטליים של קיבוטוס, פלאנה (Plana) גילתה אוסף של רשומות מסתוריות הידועות בשם יומנים דו-זמניים (Bitemporal Logs). כל יומן מורכב מ-$n$ רשומות המסומנות מ-$1$ עד $n$ ויוצרות עץ מכוון שורש. עם זאת, האילוצים המבניים משתנים בהתאם לשאלה האם זרימת הזמן היא רטרוספקטיבית (לוגיקה A) או פרוספקטיבית (לוגיקה B):

• לוגיקה A: שורש העץ הוא ברשומה $1$; לכל רשומה אחרת $i$ יש הורה $p_i$ כך ש-$p_i < i$.
• לוגיקה B: שורש העץ הוא ברשומה $n$; לכל רשומה אחרת $i$ יש הורה $q_i$ כך ש-$q_i > i$.

כדי לנתח את התכונות המבניות, פלאנה מגדירה שני סוגים של רשומות:

• קצה (Terminal): רשומה שאינה משמשת כהורה לאף רשומה אחרת.
• צומת מרכזי (Hub): רשומה המשמשת כהורה ללפחות רשומה אחרת אחת.

פלאנה הבחינה בסימטריה מושלמת הנקראת תהודה לוגית (Logical Resonance). תכונה זו מתקיימת בין יומן מלוגיקה A לבין יומן מלוגיקה B אם ורק אם:

$$\text{For every } i\text{, entry } i \text{ is a Terminal in Logic A} \iff \text{entry } i \text{ is a Hub in Logic B.}$$

פלאנה הוכיחה מתמטית שמספר היומנים התקפים מלוגיקה A ומלוגיקה B תחת אילוץ זה הוא זהה. כעת, היא מטילה עליכם לתכנן פרוטוקול תרגום אוניברסלי — פונקציה חד-חד-ערכית ועל (בייקציה) — להמרת פורמט יומן אחד למשנהו.

הערכת נכונות

הפתרון שלכם מורץ פעמיים בכל מבחן. בהרצה הראשונה, על הפתרון שלכם להמיר כל יומן מלוגיקה A ליומן מלוגיקה B המקיים את תנאי התהודה הלוגית. בהרצה השנייה, בהינתן יומן מלוגיקה B שנוצר על ידי ההרצה הראשונה שלכם, על הפתרון שלכם לשחזר בדיוק את יומן לוגיקה A המקורי.

הקלט של ההרצה השנייה מורכב מאותם יומני לוגיקה B שהוצאתם כפלט בהרצה הראשונה, ייתכן שבסדר שונה. עבור כל יומן לוגיקה B בקלט של ההרצה השנייה, עליכם להדפיס את יומן לוגיקה A המתאים לו. הפתרון שלכם ייחשב נכון אם עבור כל יומן לוגיקה B כזה, הפלט שלכם זהה לחלוטין ליומן לוגיקה A שיצר אותו בהרצה הראשונה.

כלי בדיקה מסופק כדי לסייע לכם בפיתוח ובבדיקת הפתרון שלכם.

קלט

השורה הראשונה של הקלט מכילה שני מספרים שלמים $r$ ($r \in \{1, 2\}$) ו-$T$ ($1 \le T \le 10^5$), המייצגים את מספר ההרצה ואת מספר מקרי הבדיקה.

עבור כל מקרה בדיקה, השורה הראשונה מכילה מספר שלם $n$ ($2 \le n \le 10^3$).

אם $r = 1$, השורה השנייה מכילה $n$ מספרים שלמים $p_1, p_2, \dots, p_n$ המייצגים את יומן לוגיקה A. מובטח כי $p_1 = 0$, וכי עבור $2 \le i \le n$, $1 \le p_i < i$ היא הרשומה שאליה מחוברת רשומה $i$. כאן אנו משתמשים ב-$0$ כדי לציין שלרשומה אין הורה (כלומר, היא השורש).

אחרת, אם $r = 2$, השורה השנייה מכילה $n$ מספרים שלמים $q_1, q_2, \dots, q_n$ המייצגים את יומן לוגיקה B. מובטח כי $q_n = 0$, וכי עבור $1 \le i \le n - 1$, $i < q_i \le n$ היא הרשומה שאליה מחוברת רשומה $i$.

מובטח כי סכום ערכי $n^2$ על פני כל מקרי הבדיקה אינו עולה על $10^7$.

פלט

אם $r = 1$, עבור כל מקרה בדיקה, הדפיסו $n$ מספרים שלמים מופרדים ברווח, $q_1, q_2, \dots, q_n$, המייצגים את יומן לוגיקה B המומר. חייב להתקיים $q_n = 0$, ועבור $1 \le i \le n - 1$ חייב להתקיים $i < q_i \le n$. תכונת התהודה הלוגית חייבת להתקיים: רשומה $i$ היא קצה בלוגיקה A אם ורק אם רשומה $i$ היא צומת מרכזי בלוגיקה B.

אחרת, אם $r = 2$, עבור כל מקרה בדיקה, הדפיסו $n$ מספרים שלמים מופרדים ברווח, $p_1, p_2, \dots, p_n$, המייצגים את יומן לוגיקה A המשוחזר.

דוגמה

דוגמה 1, מעבר 1

קלט

1 3
4
0 1 1 2
4
0 1 2 1
4
0 1 1 1

פלט

3 3 4 0
3 4 4 0
2 3 4 0

דוגמה 1, מעבר 2

קלט

2 3
4
2 3 4 0
4
3 3 4 0
4
3 4 4 0

פלט

0 1 1 1
0 1 1 2
0 1 2 1

הסבר לדוגמה 1

התאמה חד-חד-ערכית ועל תקפה אפשרית מוצגת להלן.