Dane jest nieukorzenione drzewo o $n$ wierzchołkach. Musisz przypisać każdemu wierzchołkowi różną wagę, tak aby wagi tworzyły permutację liczb od $1$ do $n$.
Dla dowolnego schematu przypisania rozważamy wszystkie średnice drzewa (tzn. najdłuższe ścieżki proste w drzewie). Spośród tych średnic wybieramy tę o leksykograficznie największym ciągu wag (układając wagi wierzchołków wzdłuż ścieżki po kolei i porównując je leksykograficznie).
Twoim celem jest zminimalizowanie porządku leksykograficznego ciągu wag odpowiadającego tej „leksykograficznie największej średnicy” spośród wszystkich możliwych schematów przypisania.
Wejście
Pojedynczy przypadek testowy zawiera wiele grup danych.
Pierwszy wiersz wejścia to liczba grup danych $T$ ($1 \le T \le 10^5$), oznaczająca liczbę grup danych w tym przypadku testowym.
Dla każdej grupy danych pierwszy wiersz zawiera liczbę całkowitą $n$ ($2 \le n \le 2 \cdot 10^5$), oznaczającą liczbę wierzchołków.
Kolejne $n - 1$ wierszy zawiera po dwie liczby całkowite $u, v$ ($1 \le u, v \le n$), oznaczające krawędź drzewa.
Gwarantuje się, że we wszystkich danych $\sum n \le 2 \cdot 10^5$.
Wyjście
Dla każdego zestawu danych wypisz wiersz zawierający kilka liczb całkowitych oznaczających najmniejszy możliwy porządek leksykograficzny średnicy o największym porządku leksykograficznym.
Przykład
Wejście
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
Wyjście
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