Alice und Bob haben einen Baum $T$, der aus $2N$ Knoten besteht, die von $1$ bis $2N$ nummeriert sind.

Bob hat eine ganze Zahl $K$ und möchte $N$ Paare $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ finden, sodass jede ganze Zahl von $1$ bis $2N$ in genau einem Paar vorkommt und die Summe der Abstände $\sum_{i=1}^N \text{dist}(X_i, Y_i) = K$ beträgt, wobei $\text{dist}(X_i, Y_i)$ den Abstand zwischen den Knoten $X_i$ und $Y_i$ im Baum bezeichnet, d. h. die Anzahl der Kanten auf dem (eindeutigen) Pfad zwischen $X_i$ und $Y_i$.

Alice möchte nicht, dass Bob Erfolg hat. Sie kann die folgende Operation ausführen:

• Entferne eine Kante $(U, V)$ aus $T$.
• Füge eine neue Kante $(A, B)$ hinzu, sodass $T$ ein Baum bleibt.

Beachten Sie, dass es erlaubt ist, dieselbe Kante sowohl zum Löschen als auch zum Einfügen zu wählen, was einfach zum ursprünglichen Baum führt.

Helfen Sie Alice, eine Kante $(U, V)$, die gelöscht werden soll, und eine Kante $(A, B)$, die hinzugefügt werden soll, zu finden. Wenn es mehrere Lösungen gibt, können Sie eine beliebige davon finden.

Es lässt sich beweisen, dass es unter den Bedingungen dieses Problems immer möglich ist, eine Kante zu löschen und eine Kante hinzuzufügen, sodass keine $N$ Paare $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ existieren, bei denen jede ganze Zahl von $1$ bis $2N$ in genau einem Paar vorkommt und die Summe der Abstände gleich $K$ ist.

Eingabe

Die Eingabe erfolgt im folgenden Format:

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

• Alle Eingabewerte sind ganze Zahlen.
• $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$
• Es wird garantiert, dass die gegebenen Kanten einen Baum bilden.
• Es wird garantiert, dass die Summe von $N$ über alle Testfälle hinweg $2 \times 10^5$ nicht überschreitet.

Ausgabe

Geben Sie für jeden Testfall zwei Zeilen aus:

Die erste Zeile sollte zwei ganze Zahlen $U$ und $V$ enthalten — was bedeutet, dass die Kante $(U, V)$ gelöscht werden soll.

Die zweite Zeile sollte zwei ganze Zahlen $A$ und $B$ enthalten — was bedeutet, dass die Kante $(A, B)$ hinzugefügt werden soll.

Wenn es mehrere Lösungen gibt, geben Sie eine beliebige davon aus.

Beispiel

Eingabe 1

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

Ausgabe 1

1 2
1 2
1 2
1 3

Hinweis

Testfall 1: Im ursprünglichen Baum gibt es für Bob bereits keine Möglichkeit, eine Punktzahl von $K = 20$ zu erreichen, sodass Alice einfach eine beliebige vorhandene Kante entfernen und wieder einfügen kann.

Testfall 2: Im ursprünglichen Baum gibt es für Bob eine Möglichkeit, eine Punktzahl von $K = 4$ zu erreichen, zum Beispiel durch die Wahl der Paare $(1, 4)$ und $(2, 3)$. Alice löscht die Kante $(1, 2)$ und fügt $(1, 3)$ ein. In diesem neuen Baum kann Bob keine Punktzahl von $4$ erreichen.