กำหนดต้นไม้สองต้นคือ $A$ และ $B$ ซึ่งแต่ละต้นมีจุดยอด $N$ จุด ต้นไม้ทั้งสองมีเซตของจุดยอดที่มีหมายเลขกำกับเหมือนกันคือ $\{1, 2, \dots, N\}$

สำหรับแต่ละ $i$ ($1 \le i \le N - 1$) เส้นเชื่อมที่ $i$ ของ $A$ จะเชื่อมจุดยอด $u_i$ และ $v_i$ สำหรับแต่ละ $j$ ($1 \le j \le N - 1$) เส้นเชื่อมที่ $j$ ของ $B$ จะเชื่อมจุดยอด $x_j$ และ $y_j$

สำหรับแต่ละ $i = 1, 2, \dots, N - 1$ จงแก้ปัญหาต่อไปนี้

• จงหาจำนวนเต็ม $j$ ที่ $1 \le j \le N - 1$ ซึ่งทำให้การสลับต่อไปนี้ยังคงทำให้ทั้ง $A$ และ $B$ เป็นต้นไม้:
  • ลบเส้นเชื่อมที่เชื่อมจุดยอด $u_i$ และ $v_i$ ออกจาก $A$ และลบเส้นเชื่อมที่เชื่อมจุดยอด $x_j$ และ $y_j$ ออกจาก $B$
  • จากนั้น เพิ่มเส้นเชื่อมที่เชื่อมจุดยอด $x_j$ และ $y_j$ ลงใน $A$ และเพิ่มเส้นเชื่อมที่เชื่อมจุดยอด $u_i$ และ $v_i$ ลงใน $B$

การสลับแต่ละครั้งจะถูกพิจารณาแยกกันอย่างเป็นอิสระ โดยเริ่มต้นจากต้นไม้ $A$ และ $B$ เดิม

สามารถพิสูจน์ได้ว่ามีจำนวนเต็ม $j$ ดังกล่าวอย่างน้อยหนึ่งค่าสำหรับทุกๆ $i$ ภายใต้ข้อจำกัดที่กำหนด

ข้อมูลนำเข้า

ข้อมูลนำเข้าประกอบด้วยกรณีทดสอบเดียวในรูปแบบต่อไปนี้

$$ \begin{aligned} &N \\ &u_1 \ v_1 \\ &u_2 \ v_2 \\ &\vdots \\ &u_{N-1} \ v_{N-1} \\ &x_1 \ y_1 \\ &x_2 \ y_2 \\ &\vdots \\ &x_{N-1} \ y_{N-1} \end{aligned} $$

จำนวนเต็ม $N$ คือจำนวนจุดยอดของทั้ง $A$ และ $B$ ($2 \le N \le 2 \times 10^5$)

อีก $N - 1$ บรรทัดถัดไปอธิบายเส้นเชื่อมของ $A$ สำหรับแต่ละ $i = 1, \dots, N - 1$ จำนวนเต็ม $u_i$ และ $v_i$ ($1 \le u_i, v_i \le N$) หมายความว่าเส้นเชื่อมที่ $i$ เชื่อมจุดยอด $u_i$ และ $v_i$ รับประกันว่า $A$ เป็นต้นไม้

อีก $N - 1$ บรรทัดถัดไปอธิบายเส้นเชื่อมของ $B$ สำหรับแต่ละ $j = 1, \dots, N - 1$ จำนวนเต็ม $x_j$ และ $y_j$ ($1 \le x_j, y_j \le N$) หมายความว่าเส้นเชื่อมที่ $j$ เชื่อมจุดยอด $x_j$ และ $y_j$ รับประกันว่า $B$ เป็นต้นไม้

ข้อมูลส่งออก

ส่งออก $N - 1$ บรรทัด สำหรับแต่ละ $i = 1, 2, \dots, N - 1$ บรรทัดที่ $i$ ต้องมีจำนวนเต็ม $j$ ที่สอดคล้องกับเงื่อนไขในโจทย์สำหรับเส้นเชื่อมที่ $i$ ของ $A$

หากมีคำตอบที่เป็นไปได้หลายคำตอบ คุณสามารถส่งออกคำตอบใดก็ได้

ตัวอย่าง

ข้อมูลนำเข้า 1

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

ข้อมูลส่งออก 1

1
3
2

หมายเหตุ

ในบรรทัดแรกของข้อมูลส่งออกตัวอย่าง ได้เลือก $j = 1$ สำหรับ $i = 1$ การสลับเส้นเชื่อม $(1, 3)$ ของ $A$ กับเส้นเชื่อม $(1, 2)$ ของ $B$ ทำให้ทั้ง $A$ และ $B$ ยังคงเป็นต้นไม้

สำหรับ $i = 2$ ทั้งเส้นเชื่อมของ $A$ และเส้นเชื่อมที่เลือกของ $B$ ต่างก็เป็น $(2, 4)$ ดังนั้นการสลับกันจึงไม่เปลี่ยนต้นไม้ทั้งสอง คำตอบอื่นที่ถูกต้องก็สามารถใช้ได้เช่นกัน