Gefið er órótað tré með $n$ hnútum og þú þarft að úthluta ólíkri þyngd á hvern hnút, þannig að þyngdirnar myndi umröðun talnanna frá $1$ til $n$.
Fyrir sérhverja úthlutun skoðum við öll þvermál trésins (þ.e. lengstu einföldu vegina í trénu). Meðal þessara þvermála veljum við það sem hefur stærstu þyngdarununa í stafrófsröð (með því að raða þyngdum hnútanna eftir veginum í röð og bera saman í stafrófsröð).
Markmið þitt er að lágmarka stafrófsröð þyngdarununnar sem samsvarar þessu „stærsta þvermáli í stafrófsröð“ meðal allra mögulegra úthlutana.
Inntak
Eitt prófunartilvik inniheldur marga gagnahópa.
Fyrsta lína inntaksins er fjöldi gagnahópa $T$ ($1 \le T \le 10^5$), sem táknar fjölda gagnahópa í þessu prófunartilviki.
Fyrir hvern gagnahóp inniheldur fyrsta línan heiltölu $n$ ($2 \le n \le 2 \cdot 10^5$) sem gefur til kynna fjölda hnúta.
Næstu $n - 1$ línur innihalda hver um sig tvær heiltölur $u, v$ ($1 \le u, v \le n$), sem tákna legg í trénu.
Tryggt er að yfir öll gögn gildir $\sum n \le 2 \cdot 10^5$.
Úttak
Fyrir hvert gagnasett skal prenta línu með nokkrum heiltölum sem tákna minnstu mögulegu stafrófsröð þvermálsins sem hefur stærstu stafrófsröðina.
Dæmi
Inntak
5 5 1 2 1 3 2 4 2 5 4 1 2 1 3 1 4 6 1 2 1 3 2 4 2 5 3 6 8 1 2 2 3 1 4 2 5 3 6 1 7 7 8 10 1 2 2 3 2 4 4 7 4 8 1 5 5 6 6 9 1 10
Úttak
3 4 5 1 3 4 2 3 4 5 6 1 2 3 4 5 6 1 3 4 5 6 7 8 1