Alice y Bob tienen un árbol $T$ que consta de $2N$ nodos numerados del $1$ al $2N$.

Bob tiene un entero $K$, y quiere encontrar $N$ pares $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ tales que cada entero del $1$ al $2N$ aparezca en exactamente un par y la suma de distancias sea $\sum_{i=1}^N \text{dist}(X_i, Y_i) = K$, donde $\text{dist}(X_i, Y_i)$ denota la distancia entre los nodos $X_i$ e $Y_i$ en el árbol, es decir, el número de aristas en el (único) camino entre $X_i$ e $Y_i$.

Alice no quiere que Bob tenga éxito. Ella puede realizar la siguiente operación:

• Eliminar una arista $(U, V)$ de $T$.
• Añadir una nueva arista $(A, B)$ de forma que $T$ siga siendo un árbol.

Ten en cuenta que está permitido elegir la misma arista tanto para eliminar como para insertar, lo que simplemente dará como resultado el árbol original.

Ayuda a Alice a encontrar una arista $(U, V)$ que deba eliminarse y una arista $(A, B)$ que deba añadirse. Si hay múltiples soluciones, puedes encontrar cualquiera de ellas.

Se puede demostrar que bajo las restricciones de este problema, siempre es posible eliminar una arista y añadir una arista de modo que no existan $N$ pares $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ donde cada entero del $1$ al $2N$ aparezca en exactamente un par y la suma de distancias sea igual a $K$.

Entrada

La entrada se proporciona en el siguiente formato:

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

• Todos los valores de entrada son números enteros.
• $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$
• Se garantiza que las aristas dadas forman un árbol.
• Se garantiza que la suma de $N$ en todos los casos de prueba no supera $2 \times 10^5$.

Salida

Para cada caso de prueba, imprime dos líneas:

La primera línea debe contener dos enteros $U$ y $V$, lo que significa que la arista $(U, V)$ se va a eliminar.

La segunda línea debe contener dos enteros $A$ y $B$, lo que significa que la arista $(A, B)$ se va a añadir.

Si hay múltiples soluciones, imprime cualquiera de ellas.

Ejemplo

Entrada 1

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

Salida 1

1 2
1 2
1 2
1 3

Nota

Caso de prueba 1: El árbol inicial ya no tiene forma de que Bob obtenga una puntuación de $K = 20$, por lo que Alice puede simplemente eliminar e insertar cualquier arista existente.

Caso de prueba 2: El árbol inicial tiene una forma de que Bob obtenga una puntuación de $K = 4$, por ejemplo eligiendo los pares $(1, 4)$ y $(2, 3)$. Alice elimina la arista $(1, 2)$ e inserta $(1, 3)$. En este nuevo árbol, Bob no puede obtener una puntuación de $4$.