Alice og Bob eiga tré $T$ sem samanstendur af $2N$ hnútum sem eru númeraðir frá $1$ til $2N$.

Bob er með heiltölu $K$ og vill finna $N$ pör $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ þannig að hver heiltala frá $1$ til $2N$ komi fyrir í nákvæmlega einu pari og summa fjarlægðanna sé $\sum_{i=1}^N \text{dist}(X_i, Y_i) = K$, þar sem $\text{dist}(X_i, Y_i)$ táknar fjarlægðina milli hnútanna $X_i$ og $Y_i$ í trénu, þ.e. fjölda leggja á (einstaka) veginum milli $X_i$ og $Y_i$.

Alice vill ekki að Bob takist ætlunarverk sitt. Hún getur framkvæmt eftirfarandi aðgerð:

• Fjarlægt legg $(U, V)$ úr $T$.
• Bætt við nýjum legg $(A, B)$ þannig að $T$ haldist tré.

Athugið að leyfilegt er að velja sama legginn bæði til að eyða og setja inn, sem skilar einfaldlega upphaflega trénu.

Hjálpaðu Alice að finna legg $(U, V)$ sem á að eyða og legg $(A, B)$ sem á að bæta við. Ef það eru margar lausnir máttu finna hverja sem er þeirra.

Sanna má að miðað við skorður þessa verkefnis er alltaf hægt að eyða legg og bæta við legg þannig að ekki séu til $N$ pör $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ þar sem hver heiltala frá $1$ til $2N$ kemur fyrir í nákvæmlega einu pari og summa fjarlægðanna er jöfn $K$.

Inntak

Inntakið er gefið á eftirfarandi sniði:

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

• Öll inntaksgildi eru heiltölur.
• $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$
• Það er tryggt að gefnu leggirnir myndi tré.
• Það er tryggt að summa $N$ yfir öll prófunartilvik fari ekki yfir $2 \times 10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta tvær línur:

Fyrri línan á að innihalda tvær heiltölur $U$ og $V$ — sem þýðir að eyða eigi leggnum $(U, V)$.

Seinni línan á að innihalda tvær heiltölur $A$ og $B$ — sem þýðir að bæta eigi við leggnum $(A, B)$.

Ef það eru margar lausnir skal prenta hverja sem er þeirra.

Dæmi

Inntak 1

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

Úttak 1

1 2
1 2
1 2
1 3

Athugasemd

Prófunartilvik 1: Upphaflega tréð gefur Bob þegar enga leið til að fá stigafjöldann $K = 20$, svo Alice getur einfaldlega fjarlægt og sett aftur inn hvaða legg sem er.

Prófunartilvik 2: Upphaflega tréð gefur Bob leið til að fá stigafjöldann $K = 4$, til dæmis með því að velja pörin $(1, 4)$ og $(2, 3)$. Alice eyðir leggnum $(1, 2)$ og setur inn $(1, 3)$. Í þessu nýja tré getur Bob ekki fengið stigafjöldann $4$.