Alicella ja Bobilla on puu $T$, joka koostuu $2N$ solmusta, jotka on numeroitu $1$:stä $2N$:ään.

Bobilla on kokonaisluku $K$, ja hän haluaa löytää $N$ paria $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ siten, että jokainen kokonaisluku $1$:stä $2N$:ään esiintyy täsmälleen yhdessä parissa ja etäisyyksien summa on $\sum_{i=1}^N \text{dist}(X_i, Y_i) = K$, missä $\text{dist}(X_i, Y_i)$ tarkoittaa solmujen $X_i$ ja $Y_i$ välistä etäisyyttä puussa eli kaarten lukumäärää solmujen $X_i$ ja $Y_i$ välisellä (yksikäsitteisellä) polulla.

Alice ei halua Bobin onnistuvan. Hän voi suorittaa seuraavan operaation:

• Poista kaari $(U, V)$ puusta $T$.
• Lisää uusi kaari $(A, B)$ siten, että $T$ pysyy puuna.

Huomaa, että on sallittua valita sama kaari sekä poistettavaksi että lisättäväksi, jolloin tuloksena on vain alkuperäinen puu.

Auta Alicea löytämään kaari $(U, V)$, joka tulisi poistaa, ja kaari $(A, B)$, joka tulisi lisätä. Jos ratkaisuja on useita, voit etsiä niistä minkä tahansa.

Voidaan todistaa, että tämän tehtävän rajoissa on aina mahdollista poistaa kaari ja lisätä kaari siten, ettei ole olemassa $N$ paria $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$, joissa jokainen kokonaisluku $1$:stä $2N$:ään esiintyy täsmälleen yhdessä parissa ja etäisyyksien summa on $K$.

Syöte

Syöte annetaan seuraavassa muodossa:

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

• Kaikki syötteen arvot ovat kokonaislukuja.
• $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$
• On taattu, että annetut kaaret muodostavat puun.
• On taattu, että lukujen $N$ summa yli kaikkien testitapausten ei ylitä $2 \times 10^5$.

Tuloste

Tulosta jokaista testitapausta kohden kaksi riviä:

Ensimmäisen rivin tulee sisältää kaksi kokonaislukua $U$ ja $V$ — mikä tarkoittaa, että kaari $(U, V)$ poistetaan.

Toisen rivin tulee sisältää kaksi kokonaislukua $A$ ja $B$ — mikä tarkoittaa, että kaari $(A, B)$ lisätään.

Jos ratkaisuja on useita, tulosta niistä mikä tahansa.

Esimerkki

Syöte 1

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

Tuloste 1

1 2
1 2
1 2
1 3

Huomautus

Testitapaus 1: Alkuperäisessä puussa Bobilla ei ole alun perinkään tapaa saada tulosta $K = 20$, joten Alice voi yksinkertaisesti poistaa ja lisätä takaisin minkä tahansa olemassa olevan kaaren.

Testitapaus 2: Alkuperäisessä puussa Bob voi saada tuloksen $K = 4$ esimerkiksi valitsemalla parit $(1, 4)$ ja $(2, 3)$. Alice poistaa kaaren $(1, 2)$ ja lisää kaaren $(1, 3)$. Tässä uudessa puussa Bob ei voi saada tulosta $4$.