Gegeben ist ein ungewurzelter Baum mit $n$ Knoten. Du musst jedem Knoten ein paarweise verschiedenes Gewicht zuweisen, wobei die Gewichte eine Permutation der Zahlen von $1$ bis $n$ bilden.
Für jedes Zuweisungsschema betrachten wir alle Durchmesser des Baumes (d. h. die längsten einfachen Pfade im Baum). Unter diesen Durchmessern wählen wir denjenigen mit der lexikographisch größten Gewichtsfolge aus (indem wir die Gewichte der Knoten entlang des Pfades der Reihe nach anordnen und lexikographisch vergleichen).
Dein Ziel ist es, die lexikographische Ordnung der Gewichtsfolge, die diesem „lexikographisch größten Durchmesser“ entspricht, über alle möglichen Zuweisungsschemata hinweg zu minimieren.
Eingabe
Ein einzelner Testfall enthält mehrere Datengruppen.
Die erste Zeile der Eingabe ist die Anzahl der Datengruppen $T$ ($1 \le T \le 10^5$), welche die Anzahl der Datengruppen in diesem Testfall darstellt.
Für jede Datengruppe enthält die erste Zeile eine ganze Zahl $n$ ($2 \le n \le 2 \cdot 10^5$), welche die Anzahl der Knoten angibt.
Die nächsten $n - 1$ Zeilen enthalten jeweils zwei ganze Zahlen $u, v$ ($1 \le u, v \le n$), die eine Kante des Baumes darstellen.
Es wird garantiert, dass über alle Daten hinweg $\sum n \le 2 \cdot 10^5$ gilt.
Ausgabe
Gib für jeden Datensatz eine Zeile mit mehreren ganzen Zahlen aus, welche die kleinstmögliche lexikographische Ordnung des Durchmessers mit der größten lexikographischen Ordnung darstellen.
Beispiel
Eingabe
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
Ausgabe
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