Alice และ Bob มีต้นไม้ $T$ ที่ประกอบด้วยจุดยอด $2N$ จุด ซึ่งมีหมายเลขตั้งแต่ $1$ ถึง $2N$

Bob มีจำนวนเต็ม $K$ และต้องการหาคู่ลำดับ $N$ คู่ ได้แก่ $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ โดยที่จำนวนเต็มแต่ละตัวตั้งแต่ $1$ ถึง $2N$ จะปรากฏอยู่ในคู่ลำดับเพียงหนึ่งคู่เท่านั้น และผลรวมของระยะทาง $\sum_{i=1}^N \text{dist}(X_i, Y_i) = K$ เมื่อ $\text{dist}(X_i, Y_i)$ แทนระยะทางระหว่างจุดยอด $X_i$ และ $Y_i$ ในต้นไม้ กล่าวคือ จำนวนเส้นเชื่อมบนเส้นทาง (ที่มีเพียงเส้นทางเดียว) ระหว่าง $X_i$ และ $Y_i$

Alice ไม่ต้องการให้ Bob ทำสำเร็จ เธอสามารถดำเนินการต่อไปนี้ได้:

• ลบเส้นเชื่อม $(U, V)$ ออกจาก $T$
• เพิ่มเส้นเชื่อมใหม่ $(A, B)$ โดยที่ $T$ ยังคงเป็นต้นไม้

สังเกตว่าอนุญาตให้เลือกเส้นเชื่อมเดียวกันเพื่อทั้งลบและเพิ่มกลับเข้าไปได้ ซึ่งจะทำให้ได้ต้นไม้เดิม

จงช่วย Alice หาเส้นเชื่อม $(U, V)$ ที่ควรลบออก และเส้นเชื่อม $(A, B)$ ที่ควรเพิ่มเข้าไป หากมีคำตอบหลายแบบ คุณสามารถหาคำตอบใดก็ได้

สามารถพิสูจน์ได้ว่าภายใต้ข้อจำกัดของโจทย์ข้อนี้ จะสามารถลบเส้นเชื่อมหนึ่งเส้นและเพิ่มเส้นเชื่อมหนึ่งเส้นได้เสมอ โดยที่จะไม่มีคู่ลำดับ $N$ คู่ $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ ที่แต่ละจำนวนเต็มตั้งแต่ $1$ ถึง $2N$ ปรากฏอยู่ในหนึ่งคู่พอดีและมีผลรวมระยะทางเท่ากับ $K$

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

ข้อมูลนำเข้าจะกำหนดให้ในรูปแบบต่อไปนี้:

$$T$$ $$N\ K$$ $$U_1\ V_1$$ $$U_2\ V_2$$ $$\vdots$$ $$U_{{2N-1}}\ V_{{2N-1}}$$ $$\vdots$$

• ค่าข้อมูลนำเข้าทั้งหมดเป็นจำนวนเต็ม
• $1 \le T \le 10^4$
• $2 \le N \le 2 \times 10^5$
• $1 \le K \le 10^{12}$
• $1 \le U_i, V_i \le 2N$
• รับประกันว่าเส้นเชื่อมที่กำหนดให้ประกอบกันเป็นต้นไม้
• รับประกันว่าผลรวมของ $N$ ในทุกชุดทดสอบจะไม่เกิน $2 \times 10^5$

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

สำหรับแต่ละชุดทดสอบ ให้แสดงผลสองบรรทัด:

บรรทัดแรกประกอบด้วยจำนวนเต็มสองตัวคือ $U$ และ $V$ — หมายความว่าให้ลบเส้นเชื่อม $(U, V)$

บรรทัดที่สองประกอบด้วยจำนวนเต็มสองตัวคือ $A$ และ $B$ — หมายความว่าให้เพิ่มเส้นเชื่อม $(A, B)$

หากมีคำตอบหลายแบบ ให้พิมพ์คำตอบใดก็ได้

ตัวอย่าง

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

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

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

1 2
1 2
1 2
1 3

หมายเหตุ

ชุดทดสอบที่ 1: ต้นไม้เริ่มต้นไม่มีวิธีที่ Bob จะได้คะแนน $K = 20$ อยู่แล้ว ดังนั้น Alice จึงเพียงแค่ลบและใส่เส้นเชื่อมที่มีอยู่เส้นใดก็ได้กลับเข้าไป

ชุดทดสอบที่ 2: ต้นไม้เริ่มต้นมีวิธีที่ Bob จะได้คะแนน $K = 4$ ตัวอย่างเช่น การเลือกคู่ $(1, 4)$ และ $(2, 3)$ ดังนั้น Alice จึงลบเส้นเชื่อม $(1, 2)$ และเพิ่ม $(1, 3)$ ในต้นไม้ใหม่นี้ Bob จะไม่สามารถทำคะแนนเท่ากับ $4$ ได้