У Аліси та Боба є дерево $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$.