Alice och Bob har ett träd $T$ som består av $2N$ noder numrerade från $1$ till $2N$.

Bob har ett heltal $K$ och vill hitta $N$ par $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ sådana att varje heltal från $1$ till $2N$ förekommer i exakt ett par och summan av avstånden är $\sum_{i=1}^N \text{dist}(X_i, Y_i) = K$, där $\text{dist}(X_i, Y_i)$ betecknar avståndet mellan noderna $X_i$ och $Y_i$ i trädet, dvs. antalet kanter på den (unika) vägen mellan $X_i$ och $Y_i$.

Alice vill inte att Bob ska lyckas. Hon kan utföra följande operation:

• Ta bort en kant $(U, V)$ från $T$.
• Lägg till en ny kant $(A, B)$ så att $T$ förblir ett träd.

Observera att det är tillåtet att välja samma kant för både borttagning och insättning, vilket bara resulterar i det ursprungliga trädet.

Hjälp Alice att hitta en kant $(U, V)$ som ska tas bort och en kant $(A, B)$ som ska läggas till. Om det finns flera lösningar kan du hitta vilken som helst av dem.

Det kan bevisas att under begränsningarna i detta problem är det alltid möjligt att ta bort en kant och lägga till en kant så att det inte existerar $N$ par $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ där varje heltal från $1$ till $2N$ förekommer i exakt ett par och summan av avstånden är lika med $K$.

Indata

Indata ges i följande format:

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

• Alla indatavärden är heltal.
• $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 garanteras att de givna kanterna bildar ett träd.
• Det garanteras att summan av $N$ över alla testfall inte överstiger $2 \times 10^5$.

Utdata

För varje testfall, skriv ut två rader:

Den första raden ska innehålla två heltal $U$ och $V$ — vilket betyder att kanten $(U, V)$ ska tas bort.

Den andra raden ska innehålla två heltal $A$ och $B$ — vilket betyder att kanten $(A, B)$ ska läggas till.

Om det finns flera lösningar, skriv ut vilken som helst av dem.

Exempel

Indata 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

Anmärkning

Testfall 1: Det ursprungliga trädet har redan inget sätt för Bob att få poängen $K = 20$, så Alice kan helt enkelt ta bort och sätta in vilken befintlig kant som helst.

Testfall 2: Det ursprungliga trädet har ett sätt för Bob att få poängen $K = 4$, till exempel genom att välja paren $(1, 4)$ och $(2, 3)$. Alice tar bort kanten $(1, 2)$ och sätter in $(1, 3)$. I detta nya träd kan Bob inte få poängen $4$.