Piggy (som på sin fritid leder Kommissionen för Interstellära Konnektivitetsprotokoll) står inför ett känsligt hårdvarudilemma. Det senaste kommunikationsnätet, som består av $n$ relästationer sammanbundna av $(n - 1)$ fiberoptiska länkar i en trädstruktur, är äntligen redo att tas i bruk. Systemet måste dock slås på med största försiktighet.
Aktiveringsprocessen går ut på att avfyra laserpulser längs specifika vägar. En väg definieras som den unika enkla rutten mellan två stationer. På grund av den katastrofala risken för "Kvantbakflödesinterferens" — ett fenomen som håller kommissionens jurister vakna om nätterna — måste följande protokoll följas strikt:
- Transmissionsvägar måste upprättas en i taget.
- För att förhindra strömspikar får varje nyupprättad väg dela högst en station med mängden av stationer som redan aktiverats av någon tidigare väg.
Formellt, låt $S$ vara mängden av för närvarande aktiverade stationer. För varje ny väg $P$ bestående av en mängd stationer $V(P)$ måste villkoret $|V(P) \cap S| \le 1$ gälla. När en väg väl har avfyrats framgångsrikt räknas alla stationer längs den vägen som en del av den aktiverade mängden $S$.
Ditt uppdrag, om du väljer att acceptera det, är att bestämma det minsta antalet laserpulser som krävs för att aktivera varje station i hela nätverket och ange en sådan följd av vägar för att tillfredsställa juristavdelningen.

Illustration av de två första exempeltestfallen. Notera att i Fall 2 delar den andra pulsen endast station $2$ med den första, vilket uppfyller regeln om icke-interferens.
Indata
Det finns flera testfall. Den första raden i indatan innehåller ett heltal $T$ ($1 \le T \le 10^4$) som anger antalet testfall. För varje testfall:
Den första raden innehåller ett heltal $n$ ($2 \le n \le 3 \times 10^5$), antalet stationer i nätet.
På de följande $(n - 1)$ raderna innehåller den $i$-te raden två heltal $u_i$ och $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), som beskriver en dubbelriktad fiberoptisk länk mellan station $u_i$ och station $v_i$.
Det garanteras att länkarna bildar ett träd och att summan av $n$ över alla testfall inte överstiger $3 \times 10^5$.
Utdata
För varje testfall, skriv ut det minsta antalet vägar $k$ på den första raden. Därefter, skriv ut $k$ rader som var och en innehåller två heltal $a_i$ och $b_i$, vilka representerar ändpunkterna för den $i$-te vägen i följden. Notera att $a_i$ kan vara lika med $b_i$ om vägen består av en enda station.
Om det finns flera optimala följder accepteras vilken som helst som strikt följer icke-interferensprotokollet.
Exempel
Indata
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