Alice e Bob hanno un albero $T$ composto da $2N$ nodi numerati da $1$ a $2N$.

Bob ha un intero $K$, e vuole trovare $N$ coppie $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ tali che ogni intero da $1$ a $2N$ compaia in esattamente una coppia e la somma delle distanze sia $\sum_{i=1}^N \text{dist}(X_i, Y_i) = K$, dove $\text{dist}(X_i, Y_i)$ indica la distanza tra i nodi $X_i$ e $Y_i$ nell'albero, cioè il numero di archi sul cammino (unico) tra $X_i$ e $Y_i$.

Alice non vuole che Bob ci riesca. Può eseguire la seguente operazione:

• Rimuovere un arco $(U, V)$ da $T$.
• Aggiungere un nuovo arco $(A, B)$ in modo che $T$ rimanga un albero.

Nota che è consentito scegliere lo stesso arco sia da eliminare che da inserire, il che produrrà semplicemente l'albero originale.

Aiuta Alice a trovare un arco $(U, V)$ da eliminare e un arco $(A, B)$ da aggiungere. Se ci sono più soluzioni, puoi trovarne una qualsiasi.

Si può dimostrare che, sotto i vincoli di questo problema, è sempre possibile eliminare un arco e aggiungere un arco in modo che non esistano $N$ coppie $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ in cui ogni intero da $1$ a $2N$ compare in esattamente una coppia e la somma delle distanze è uguale a $K$.

Input

L'input è fornito nel seguente formato:

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

• Tutti i valori in input sono interi.
• $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$
• È garantito che gli archi forniti formino un albero.
• È garantito che la somma di $N$ su tutti i casi di test non superi $2 \times 10^5$.

Output

Per ogni caso di test, stampa due righe:

La prima riga deve contenere due interi $U$ e $V$ — a indicare che l'arco $(U, V)$ deve essere eliminato.

La seconda riga deve contenere due interi $A$ e $B$ — a indicare che l'arco $(A, B)$ deve essere aggiunto.

Se ci sono più soluzioni, stampane una qualsiasi.

Esempio

Input 1

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

Output 1

1 2
1 2
1 2
1 3

Note

Caso di test 1: L'albero iniziale non offre già alcun modo a Bob per ottenere un punteggio di $K = 20$, quindi Alice può semplicemente rimuovere e reinserire qualsiasi arco esistente.

Caso di test 2: L'albero iniziale offre a Bob un modo per ottenere un punteggio di $K = 4$, ad esempio scegliendo le coppie $(1, 4)$ e $(2, 3)$. Alice elimina l'arco $(1, 2)$ e inserisce $(1, 3)$. In questo nuovo albero, Bob non può ottenere un punteggio di $4$.