Piggy (sem í frítíma sínum stýrir Nefnd um samskiptastaðla milli stjarna) stendur frammi fyrir vandasamri vélbúnaðarþraut. Nýjasta fjarskiptanetið, sem samanstendur af $n$ endurvarpsstöðvum sem tengdar eru saman með $(n - 1)$ ljósleiðaratengingum í trjágrind, er loksins tilbúið til uppsetningar. Hins vegar verður að ræsa kerfið með ýtrustu aðgát.
Virkjunarferlið felst í því að skjóta leysipúlsum eftir ákveðnum vegum. Vegur er skilgreindur sem hinn ótvíræði einfaldi vegur milli tveggja stöðva. Vegna hættunnar á „skammtafræðilegri bakflæðistruflun“ — fyrirbæri sem heldur lögfræðingum nefndarinnar andvaka á nóttunni — verður að fylgja eftirfarandi reglum í hvívetna:
- Koma verður á sendingarvegum einum í einu.
- Til að koma í veg fyrir álagsbylgjur má hver nýr vegur deila í mesta lagi einni stöð með mengi þeirra stöðva sem þegar hafa verið virkjaðar af fyrri vegum.
Formlega, látum $S$ vera mengi þeirra stöðva sem nú eru virkar. Fyrir hvern nýjan veg $P$ sem samanstendur af mengi stöðva $V(P)$ verður skilyrðið $|V(P) \cap S| \le 1$ að gilda. Um leið og búið er að skjóta púlsi eftir vegi teljast allar stöðvar á þeim vegi hluti af virkjaða menginu $S$.
Verkefni þitt, ef þú kýst að taka því, er að ákvarða lágmarksfjölda leysipúlsa sem þarf til að virkja sérhverja stöð í öllu netinu og gefa upp eina slíka runu af vegum til að friða lögfræðideildina.

Skýringarmynd af fyrstu tveimur prófunartilvikunum í dæminu. Athugið að í Tilviki 2 deilir annar púlsinn aðeins stöð $2$ með þeim fyrsta, sem uppfyllir regluna um truflanaleysi.
Inntak
Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur heiltölu $T$ ($1 \le T \le 10^4$) sem gefur til kynna fjölda prófunartilvika. Fyrir hvert prófunartilvik:
Fyrsta línan inniheldur heiltölu $n$ ($2 \le n \le 3 \times 10^5$), fjölda stöðva í netinu.
Í næstu $(n - 1)$ línum inniheldur $i$-ta línan tvær heiltölur $u_i$ og $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), sem lýsa tvístefnu ljósleiðaratengingu milli stöðvar $u_i$ og stöðvar $v_i$.
Tryggt er að tengingarnar myndi tré og að summa $n$ yfir öll prófunartilvik fari ekki yfir $3 \times 10^5$.
Úttak
Fyrir hvert prófunartilvik skal prenta lágmarksfjölda vega $k$ á fyrstu línuna. Þar á eftir skal prenta $k$ línur, þar sem hver lína inniheldur tvær heiltölur $a_i$ og $b_i$ sem tákna endapunkta $i$-ta vegarins í rununni. Athugið að $a_i$ má vera jafnt $b_i$ ef vegurinn samanstendur af einni stöð.
Ef fleiri en ein ákjósanleg runa er til verður hvaða runa sem er, sem fylgir reglunni um truflanaleysi í hvívetna, samþykkt.
Dæmi
Inntak
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
Úttak
1 1 3 2 4 5 1 3 3 7 7 1 6 4 5