لدى أليس وبوب شجرة $T$ تتكون من $2N$ عقدة مرقمة من $1$ إلى $2N$.

لدى بوب عدد صحيح $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$.

لا تريد أليس أن ينجح بوب. يمكنها إجراء العملية التالية:

• إزالة حافة $(U, V)$ من $T$.
• إضافة حافة جديدة $(A, B)$ بحيث تظل $T$ شجرة.

لاحظ أنه يُسمح باختيار نفس الحافة لحذفها وإعادة إدراجها، مما سيؤدي ببساطة إلى بقاء الشجرة الأصلية كما هي.

ساعد أليس في إيجاد حافة $(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: الشجرة الابتدائية لا تتيح لبوب أصلًا أي طريقة للحصول على مجموع $K = 20$، لذا يمكن لأليس ببساطة إزالة وإدراج أي حافة موجودة.

حالة الاختبار 2: الشجرة الابتدائية تتيح لبوب طريقة للحصول على مجموع $K = 4$، على سبيل المثال عن طريق اختيار الزوجين $(1, 4)$ و $(2, 3)$. تحذف أليس الحافة $(1, 2)$ وتدرج $(1, 3)$. في هذه الشجرة الجديدة، لا يمكن لبوب الحصول على مجموع $4$.