Дано некорневое дерево с $n$ вершинами. Вам нужно присвоить каждой вершине различный вес так, чтобы веса образовывали перестановку чисел от $1$ до $n$.
Для любой схемы присвоения весов рассмотрим все диаметры дерева (то есть самые длинные простые пути в дереве). Среди этих диаметров выберем тот, у которого лексикографически наибольшая последовательность весов (выписывая веса вершин вдоль пути по порядку и сравнивая их лексикографически).
Ваша цель — минимизировать лексикографический порядок последовательности весов, соответствующей этому «лексикографически наибольшему диаметру», среди всех возможных схем присвоения весов.
Входные данные
Один тест содержит несколько групп данных.
В первой строке входных данных записано количество групп данных $T$ ($1 \le T \le 10^5$), представляющее число групп данных в этом тесте.
Для каждой группы данных первая строка содержит целое число $n$ ($2 \le n \le 2 \cdot 10^5$), указывающее количество вершин.
Следующие $n - 1$ строк содержат по два целых числа $u, v$ ($1 \le u, v \le n$), обозначающих ребро дерева.
Гарантируется, что по всем наборам данных $\sum n \le 2 \cdot 10^5$.
Выходные данные
Для каждого набора данных выведите строку из нескольких целых чисел, представляющую наименьший возможный лексикографический порядок диаметра с наибольшим лексикографическим порядком.
Пример
Входные данные
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
Выходные данные
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