هذه مسألة متعددة المراحل (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 الصالحة تحت هذا القيد متطابق تمامًا. والآن، تكلّفك بتصميم بروتوكول ترجمة شامل — أي دالة تقابل (bijection) — لتحويل إحدى صيغتي السجلات إلى الأخرى.

تقييم الصحة

يتم تنفيذ حلك مرتين في كل اختبار. في التشغيل الأول، يجب على حلك تحويل كل سجل من المنطق 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

يوضح الشكل أدناه تقابلًا صالحًا ممكنًا.