Alice og Bob har et tre $T$ som består av $2N$ noder nummerert fra $1$ til $2N$.

Bob har et heltall $K$, og ønsker å finne $N$ par $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ slik at hvert heltall fra $1$ til $2N$ forekommer i nøyaktig ett par og summen av avstandene er $\sum_{i=1}^N \text{dist}(X_i, Y_i) = K$, der $\text{dist}(X_i, Y_i)$ betegner avstanden mellom nodene $X_i$ og $Y_i$ i treet, dvs. antall kanter på den (unike) stien mellom $X_i$ og $Y_i$.

Alice vil ikke at Bob skal lykkes. Hun kan utføre følgende operasjon:

• Fjerne en kant $(U, V)$ fra $T$.
• Legge til en ny kant $(A, B)$ slik at $T$ forblir et tre.

Merk at det er tillatt å velge samme kant for både sletting og innsetting, noe som bare vil resultere i det opprinnelige treet.

Hjelp Alice med å finne en kant $(U, V)$ som bør slettes og en kant $(A, B)$ som bør legges til. Hvis det finnes flere løsninger, kan du finne hvilken som helst av dem.

Det kan bevises at under begrensningene i denne oppgaven er det alltid mulig å slette en kant og legge til en kant slik at det ikke finnes $N$ par $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ der hvert heltall fra $1$ til $2N$ forekommer i nøyaktig ett par og summen av avstandene er lik $K$.

Inndata

Inndataene er gitt i følgende format:

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

• Alle inndataverdier er heltall.
• $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$
• Det er garantert at de oppgitte kantene danner et tre.
• Det er garantert at summen av $N$ over alle testtilfeller ikke overstiger $2 \times 10^5$.

Utdata

For hvert testtilfelle skal du skrive ut to linjer:

Den første linjen skal inneholde to heltall $U$ og $V$ — som betyr at kanten $(U, V)$ skal slettes.

Den andre linjen skal inneholde to heltall $A$ og $B$ — som betyr at kanten $(A, B)$ skal legges til.

Hvis det finnes flere løsninger, kan du skrive ut hvilken som helst av dem.

Eksempel

Inndata 1

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

Utdata 1

1 2
1 2
1 2
1 3

Merk

Testtilfelle 1: Det opprinnelige treet har allerede ingen måte for Bob å oppnå en poengsum på $K = 20$, så Alice kan ganske enkelt fjerne og sette inn en hvilken som helst eksisterende kant.

Testtilfelle 2: Det opprinnelige treet har en måte for Bob å oppnå en poengsum på $K = 4$, for eksempel ved å velge parene $(1, 4)$ og $(2, 3)$. Alice sletter kanten $(1, 2)$ og setter inn $(1, 3)$. I dette nye treet kan ikke Bob oppnå en poengsum på $4$.