Étant donné un arbre non enraciné à $n$ nœuds, vous devez attribuer un poids distinct à chaque nœud, les poids formant une permutation des nombres de $1$ à $n$.
Pour tout schéma d'attribution, nous considérons tous les diamètres de l'arbre (c'est-à-dire les plus longs chemins simples dans l'arbre). Parmi ces diamètres, nous sélectionnons celui qui possède la séquence de poids lexicographiquement la plus grande (en disposant dans l'ordre les poids des nœuds le long du chemin et en les comparant selon l'ordre lexicographique).
Votre objectif est de minimiser l'ordre lexicographique de la séquence de poids correspondant à ce « diamètre lexicographiquement le plus grand » parmi tous les schémas d'attribution possibles.
Entrée
Un seul cas de test contient plusieurs groupes de données.
La première ligne de l'entrée est le nombre de groupes de données $T$ ($1 \le T \le 10^5$), représentant le nombre de groupes de données dans ce cas de test.
Pour chaque groupe de données, la première ligne contient un entier $n$ ($2 \le n \le 2 \cdot 10^5$) indiquant le nombre de nœuds.
Les $n - 1$ lignes suivantes contiennent chacune deux entiers $u, v$ ($1 \le u, v \le n$), représentant une arête de l'arbre.
Il est garanti que sur l'ensemble des données, $\sum n \le 2 \cdot 10^5$.
Sortie
Pour chaque jeu de données, affichez une ligne contenant plusieurs entiers représentant le plus petit ordre lexicographique possible du diamètre ayant le plus grand ordre lexicographique.
Exemple
Entrée
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
Sortie
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