Givet ett orotat träd med $n$ noder ska du tilldela en distinkt vikt till varje nod, så att vikterna bildar en permutation av talen från $1$ till $n$.
För varje tilldelningsschema betraktar vi alla diametrar i trädet (dvs. den längsta enkla vägen i trädet). Bland dessa diametrar väljer vi den som har den lexikografiskt största viktsekvensen (genom att ordna nodernas vikter längs vägen i följd och jämföra dem lexikografiskt).
Ditt mål är att minimera den lexikografiska ordningen för viktsekvensen som motsvarar denna "lexikografiskt största diameter" bland alla möjliga tilldelningsscheman.
Indata
Ett enskilt testfall innehåller flera datagrupper.
Den första raden i indatan är antalet datagrupper $T$ ($1 \le T \le 10^5$), vilket representerar antalet datagrupper i detta testfall.
För varje datagrupp innehåller den första raden ett heltal $n$ ($2 \le n \le 2 \cdot 10^5$) som anger antalet noder.
De följande $n - 1$ raderna innehåller var och en två heltal $u, v$ ($1 \le u, v \le n$), som representerar en kant i trädet.
Det garanteras att över all data gäller $\sum n \le 2 \cdot 10^5$.
Utdata
För varje datamängd, skriv ut en rad med flera heltal som representerar den minsta möjliga lexikografiska ordningen för diametern med den största lexikografiska ordningen.
Exempel
Indata
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