โจทย์ข้อนี้เป็นโจทย์แบบหลายรอบ (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

การจับคู่แบบหนึ่งต่อหนึ่งทั่วถึงที่ถูกต้องแบบหนึ่งแสดงอยู่ด้านล่าง