Alice et Bob ont un arbre $T$ composé de $2N$ nœuds numérotés de $1$ à $2N$.

Bob a un entier $K$, et souhaite trouver $N$ paires $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ telles que chaque entier de $1$ à $2N$ apparaisse dans exactement une paire et que la somme des distances vérifie $\sum_{i=1}^N \text{dist}(X_i, Y_i) = K$, où $\text{dist}(X_i, Y_i)$ désigne la distance entre les nœuds $X_i$ et $Y_i$ dans l'arbre, c'est-à-dire le nombre d'arêtes sur le (seul) chemin entre $X_i$ et $Y_i$.

Alice ne veut pas que Bob réussisse. Elle peut effectuer l'opération suivante :

• Supprimer une arête $(U, V)$ de $T$.
• Ajouter une nouvelle arête $(A, B)$ de sorte que $T$ reste un arbre.

Notez qu'il est permis de choisir la même arête pour la suppression et l'insertion, ce qui redonnera simplement l'arbre d'origine.

Aidez Alice à trouver une arête $(U, V)$ à supprimer et une arête $(A, B)$ à ajouter. S'il existe plusieurs solutions, vous pouvez en trouver une quelconque.

On peut prouver que sous les contraintes de ce problème, il est toujours possible de supprimer une arête et d'en ajouter une de telle sorte qu'il n'existe pas $N$ paires $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ où chaque entier de $1$ à $2N$ apparaît dans exactement une paire et dont la somme des distances vaut $K$.

Entrée

L'entrée est donnée dans le format suivant :

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

• Toutes les valeurs d'entrée sont des entiers.
• $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$
• Il est garanti que les arêtes données forment un arbre.
• Il est garanti que la somme de $N$ sur tous les cas de test ne dépasse pas $2 \times 10^5$.

Sortie

Pour chaque cas de test, affichez deux lignes :

La première ligne doit contenir deux entiers $U$ et $V$ — signifiant que l'arête $(U, V)$ doit être supprimée.

La deuxième ligne doit contenir deux entiers $A$ et $B$ — signifiant que l'arête $(A, B)$ doit être ajoutée.

S'il existe plusieurs solutions, affichez-en une quelconque.

Exemple

Entrée 1

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

Sortie 1

1 2
1 2
1 2
1 3

Note

Cas de test 1 : L'arbre initial ne permet déjà pas à Bob d'obtenir un score de $K = 20$, donc Alice peut simplement supprimer et réinsérer n'importe quelle arête existante.

Cas de test 2 : L'arbre initial permet à Bob d'obtenir un score de $K = 4$, par exemple en choisissant les paires $(1, 4)$ et $(2, 3)$. Alice supprime l'arête $(1, 2)$ et insère $(1, 3)$. Dans ce nouvel arbre, Bob ne peut pas obtenir un score de $4$.