Annettuna on juureton puu, jossa on $n$ solmua. Sinun tulee asettaa jokaiselle solmulle eri paino siten, että painot muodostavat lukujen $1$:stä $n$:ään permutaation.
Mille tahansa painojen asetustavalle tarkastelemme kaikkia puun halkaisijoita (eli puun pisimpiä yksinkertaisia polkuja). Näiden halkaisijoiden joukosta valitsemme sen, jolla on leksikografisesti suurin painojono (järjestämällä polun varrella olevien solmujen painot järjestykseen ja vertailemalla niitä leksikografisesti).
Tavoitteenasi on minimoida tätä "leksikografisesti suurinta halkaisijaa" vastaavan painojonon leksikografinen järjestys kaikkien mahdollisten asetustapojen joukossa.
Syöte
Yksi testitapaus sisältää useita tietoryhmiä.
Syötteen ensimmäinen rivi on tietoryhmien lukumäärä $T$ ($1 \le T \le 10^5$), joka ilmaisee tietoryhmien määrän tässä testitapauksessa.
Jokaiselle tietoryhmälle ensimmäinen rivi sisältää kokonaisluvun $n$ ($2 \le n \le 2 \cdot 10^5$), joka ilmaisee solmujen lukumäärän.
Seuraavat $n - 1$ riviä sisältävät kukin kaksi kokonaislukua $u, v$ ($1 \le u, v \le n$), jotka kuvaavat puun kaarta.
On taattua, että yli kaikkien tietoryhmien $\sum n \le 2 \cdot 10^5$.
Tuloste
Tulosta jokaista tietoaineistoa kohden rivi, jolla on useita kokonaislukuja, jotka kuvaavat leksikografiselta järjestykseltään suurimman halkaisijan pienintä mahdollista leksikografista järjestystä.
Esimerkki
Syöte
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
Tuloste
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