Piggy (joka vapaa-ajallaan johtaa Tähtienvälisen Yhteyskäytäntökomission toimintaa) on hankalan laitteisto-ongelman edessä. Uusin viestintäverkko, joka koostuu $n$ linkkiasemasta ja niitä puurakenteeksi yhdistävästä $(n - 1)$ valokuituyhteydestä, on vihdoin valmis käyttöönottoon. Järjestelmä on kuitenkin käynnistettävä äärimmäisen varovasti.
Aktivointiprosessissa ammutaan laserpulsseja tiettyjä polkuja pitkin. Polku määritellään kahden aseman väliseksi yksikäsitteiseksi yksinkertaiseksi reitiksi. ”Kvanttitakaisinvirtausinterferenssin” – ilmiön, joka pitää komission lakimiehetvalveilla öisin – aiheuttaman katastrofaalisen riskin vuoksi seuraavaa protokollaa on noudatettava tiukasti:
- Siirtopolut on muodostettava yksi kerrallaan.
- Virtapiikkien estämiseksi jokainen uutena muodostettava polku saa sisältää enintään yhden yhteisen aseman aiempien polkujen jo aktivoimien asemien joukon kanssa.
Muodollisesti olkoon $S$ tällä hetkellä aktivoitujen asemien joukko. Jokaiselle uudelle polulle $P$, joka koostuu asemajoukosta $V(P)$, on pädettävä ehdon $|V(P) \cap S| \le 1$. Kun polku on onnistuneesti aktivoitu pulssilla, kaikki kyseisen polun varrella olevat asemat katsotaan osaksi aktivoitua joukkoa $S$.
Tehtäväsi, jos päätät ottaa sen vastaan, on määrittää pienin mahdollinen laserpulssien määrä, joka tarvitaan koko verkon jokaisen aseman aktivoimiseen, ja esittää yksi tällainen polkujen jono lakiosaston tyydyttämiseksi.

Kahden ensimmäisen esimerkkitestitapauksen havainnollistus. Huomaa, että tapauksessa 2 toinen pulssi jakaa ensimmäisen kanssa vain aseman $2$, mikä täyttää häiriöttömyyssäännön.
Syöte
Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^4$), joka ilmoittaa testitapausten lukumäärän. Jokaisessa testitapauksessa:
Ensimmäinen rivi sisältää kokonaisluvun $n$ ($2 \le n \le 3 \times 10^5$), verkossa olevien asemien lukumäärän.
Seuraavilla $(n - 1)$ rivillä $i$-s rivi sisältää kaksi kokonaislukua $u_i$ ja $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), jotka kuvaavat kaksisuuntaista valokuituyhteyttä aseman $u_i$ ja aseman $v_i$ välillä.
On taattu, että yhteydet muodostavat puun ja että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $3 \times 10^5$.
Tuloste
Tulosta jokaista testitapausta kohden ensimmäiselle riville pienin polkujen lukumäärä $k$. Tulosta tämän jälkeen $k$ riviä, joista jokainen sisältää kaksi kokonaislukua $a_i$ ja $b_i$, jotka esittävät jonon $i$-nnen polun päätepisteitä. Huomaa, että $a_i$ voi olla yhtä suuri kuin $b_i$, jos polku koostuu yhdestä ainoasta asemasta.
Jos optimaalisia jonoja on useita, mikä tahansa häiriöttömyysprotokollaa tiukasti noudattava jono hyväksytään.
Esimerkki
Syöte
3 3 1 2 2 3 5 1 2 2 3 2 4 2 5 7 1 2 1 3 2 4 2 5 3 6 3 7
Tuloste
1 1 3 2 4 5 1 3 3 7 7 1 6 4 5