Gitt et urotet tre med $n$ noder må du tilordne en distinkt vekt til hver node, der vektene danner en permutasjon av tallene fra $1$ til $n$.
For enhver tilordningsplan betrakter vi alle diametre i treet (dvs. den lengste enkle stien i treet). Blant disse diametrene velger vi den som har den leksikografisk største vektsekvensen (ved å ordne vektene til nodene langs stien i rekkefølge og sammenligne leksikografisk).
Målet ditt er å minimere den leksikografiske ordningen til vektsekvensen som tilsvarer denne «leksikografisk største diameteren» blant alle mulige tilordningsplaner.
Inndata
Ett enkelt testtilfelle inneholder flere datagrupper.
Den første linjen i inndataene er antall datagrupper $T$ ($1 \le T \le 10^5$), som representerer antall datagrupper i dette testtilfellet.
For hver datagruppe inneholder den første linjen et heltall $n$ ($2 \le n \le 2 \cdot 10^5$) som angir antall noder.
De neste $n - 1$ linjene inneholder hver to heltall $u, v$ ($1 \le u, v \le n$), som representerer en kant i treet.
Det er garantert at på tvers av alle data er $\sum n \le 2 \cdot 10^5$.
Utdata
For hvert datasett skal du skrive ut en linje med flere heltall som representerer den minste mulige leksikografiske ordningen til diameteren med den største leksikografiske ordningen.
Eksempel
Inndata
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
Utdata
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