לאליס ולבוב יש עץ $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$.