Alice i Bob mają drzewo $T$ składające się z $2N$ wierzchołków ponumerowanych od $1$ do $2N$.

Bob ma liczbę całkowitą $K$ i chce znaleźć $N$ par $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ takich, że każda liczba całkowita od $1$ do $2N$ występuje w dokładnie jednej parze, a suma odległości wynosi $\sum_{i=1}^N \text{dist}(X_i, Y_i) = K$, gdzie $\text{dist}(X_i, Y_i)$ oznacza odległość między wierzchołkami $X_i$ oraz $Y_i$ w drzewie, tj. liczbę krawędzi na (jedynej) ścieżce między $X_i$ a $Y_i$.

Alice nie chce, aby Bobowi się udało. Może ona wykonać następującą operację:

• Usunąć krawędź $(U, V)$ z $T$.
• Dodać nową krawędź $(A, B)$ tak, aby $T$ pozostało drzewem.

Zauważ, że dozwolone jest wybranie tej samej krawędzi do usunięcia i wstawienia, co po prostu pozostawi oryginalne drzewo bez zmian.

Pomóż Alice znaleźć krawędź $(U, V)$, którą należy usunąć, oraz krawędź $(A, B)$, którą należy dodać. Jeśli istnieje wiele rozwiązań, możesz znaleźć dowolne z nich.

Można udowodnić, że przy ograniczeniach tego zadania zawsze można usunąć krawędź i dodać krawędź tak, aby nie istniało $N$ par $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$, w których każda liczba całkowita od $1$ do $2N$ występuje w dokładnie jednej parze, a suma odległości jest równa $K$.

Wejście

Wejście jest podane w następującym formacie:

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

• Wszystkie wartości wejściowe są liczbami całkowitymi.
• $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$
• Gwarantuje się, że podane krawędzie tworzą drzewo.
• Gwarantuje się, że suma $N$ we wszystkich przypadkach testowych nie przekracza $2 \times 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz dwa wiersze:

Pierwszy wiersz powinien zawierać dwie liczby całkowite $U$ oraz $V$ — oznaczające, że krawędź $(U, V)$ ma zostać usunięta.

Drugi wiersz powinien zawierać dwie liczby całkowite $A$ oraz $B$ — oznaczające, że krawędź $(A, B)$ ma zostać dodana.

Jeśli istnieje wiele rozwiązań, wypisz dowolne z nich.

Przykład

Wejście 1

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

Wyjście 1

1 2
1 2
1 2
1 3

Uwaga

Przypadek testowy 1: Początkowe drzewo już nie daje Bobowi możliwości uzyskania wyniku $K = 20$, więc Alice może po prostu usunąć i wstawić dowolną istniejącą krawędź.

Przypadek testowy 2: Początkowe drzewo daje Bobowi możliwość uzyskania wyniku $K = 4$, na przykład poprzez wybranie par $(1, 4)$ oraz $(2, 3)$. Alice usuwa krawędź $(1, 2)$ i wstawia $(1, 3)$. W tym nowym drzewie Bob nie może uzyskać wyniku $4$.