Piggy (som på fritiden leder Kommisjonen for Interstellare Tilkoblingsprotokoller) står overfor en vrien maskinvareutfordring. Det nyeste kommunikasjonsnettet, som består av $n$ reléstasjoner forbundet med $(n - 1)$ fiberoptiske linjer i en trestruktur, er endelig klart til bruk. Systemet må imidlertid slås på med ekstrem varsomhet.
Aktiveringsprosessen innebærer å sende ut laserpulser langs bestemte stier. En sti er definert som den unike enkle ruten mellom to stasjoner. På grunn av den katastrofale risikoen for «Kvantetilbakestrømsinterferens» — et fenomen som holder kommisjonens advokater våkne om natten — må følgende protokoll følges strengt:
- Transmisjonsstier må opprettes én etter én.
- For å forhindre strømtopper kan hver nyopprettede sti dele høyst én stasjon med mengden av stasjoner som allerede er aktivert av en tidligere sti.
Formelt, la $S$ være mengden av stasjoner som for øyeblikket er aktivert. For enhver ny sti $P$ som består av en mengde stasjoner $V(P)$, må betingelsen $|V(P) \cap S| \le 1$ gjelde. Så snart en sti er vellykket aktivert, regnes alle stasjoner langs stien som en del av den aktiverte mengden $S$.
Ditt oppdrag, dersom du velger å akseptere det, er å bestemme det minimale antallet laserpulser som kreves for å aktivere hver eneste stasjon i hele nettverket, og oppgi en slik sekvens av stier for å tilfredsstille den juridiske avdelingen.

Illustrasjon av de to første eksempeltesttilfellene. Merk at i Tilfelle 2 deler den andre pulsen kun stasjon $2$ med den første, noe som oppfyller regelen om ikke-interferens.
Inndata
Det er flere testtilfeller. Den første linjen i inndataene inneholder et heltall $T$ ($1 \le T \le 10^4$) som angir antall testtilfeller. For hvert testtilfelle:
Den første linjen inneholder et heltall $n$ ($2 \le n \le 3 \times 10^5$), antallet stasjoner i nettet.
I de følgende $(n - 1)$ linjene inneholder den $i$-te linjen to heltall $u_i$ og $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), som beskriver en toveis fiberoptisk linje mellom stasjon $u_i$ og stasjon $v_i$.
Det garanteres at linjene danner et tre, og at summen av $n$ over alle testtilfeller ikke overstiger $3 \times 10^5$.
Utdata
For hvert testtilfelle skal du skrive ut det minimale antallet stier $k$ på den første linjen. Deretter skriver du ut $k$ linjer som hver inneholder to heltall $a_i$ og $b_i$, som representerer endepunktene til den $i$-te stien i sekvensen. Merk at $a_i$ kan være lik $b_i$ dersom stien består av én enkelt stasjon.
Hvis det finnes flere optimale sekvenser, vil enhver sekvens som strengt følger ikke-interferensprotokollen bli godtatt.
Eksempel
Inndata
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
Utdata
1 1 3 2 4 5 1 3 3 7 7 1 6 4 5