D. Деревонумерация
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Eikooc и Sushi играют в игру.

Игра проводится на дереве из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$. Напомним, что дерево с $$$n$$$ вершинами это неориентированный связный граф с $$$n-1$$$ ребрами.

Игроки поочередно перемещают фишку по дереву. Eikooc делает первый ход, помещая фишку на любую вершину по своему выбору. Sushi делает следующий ход, затем Eikooc, затем Sushi, и так далее. В каждый ход после первого, игрок должен переместить фишку в какую-то вершину $$$u$$$ такую, что:

  • Между вершинами $$$u$$$ и $$$v$$$ (на которой фишка находится данный момент), есть ребро
  • $$$u$$$ не была посещена ранее
  • $$$u \oplus v \leq min(u, v)$$$

Здесь $$$x \oplus y$$$ обозначает операцию побитового исключающего ИЛИ чисел $$$x$$$ и $$$y$$$.

Оба игрока играют оптимально. Игрок, который не может сделать ход, проигрывает.

Ниже приведены примеры, демонстрирующие правила игры.

Предположим, Eikooc начинает игру, помещая фишку в вершину $$$4$$$. Затем Sushi перемещает фишку в вершину $$$6$$$, которая не была посещена и является соседней к $$$4$$$. Также $$$6 \oplus 4 = 2 \leq min(6, 4)$$$. На следующем ходу Eikooc перемещает фишку в вершину $$$5$$$, которая не была посещена и является соседней к $$$6$$$. Также, $$$5 \oplus 6 = 3 \leq min(5, 6)$$$. У Sushi больше нет ходов для игры, поэтому она проигрывает.
Предположим, Eikooc начинает игру, помещая фишку в вершинул $$$3$$$. Sushi перемещает фишку в вершину $$$2$$$, которая не была посещена и является соседней к $$$3$$$. Также $$$3 \oplus 2 = 1 \leq min(3, 2)$$$. Eikooc не может переместить фишку в вершину $$$6$$$, так как $$$6 \oplus 2 = 4 \nleq min(6, 2)$$$. Поскольку у Eikooc нет ходов для игры, она проигрывает.

Перед началом игры Eikooc решает тайком перенумеровать вершины дерева в свою пользу. Формально, перенумерация — это перестановка $$$p$$$ длины $$$n$$$ (последовательность из $$$n$$$ целых чисел, где каждое целое число от $$$1$$$ до $$$n$$$ встречается ровно один раз), где $$$p_i$$$ обозначает новый номер вершины $$$i$$$.

Она хочет максимизировать количество вершин, которые она может выбрать в первый ход, для которых она сможет гарантировать себе победу. Помогите Eikooc найти любую перенумерацию, которая поможет ей в этом.

Входные данные

Первая строка содержит одно целое число $$$t~(1 \le t \le 10^5)$$$  — количество наборов входных данных. Описание каждого набора входных данных выглядит следующим образом.

Первая строка каждого набора входных данных содержит целое число $$$n~(1 \le n \le 2 \cdot 10^5)$$$  — количество вершин в дереве.

Следующие $$$n-1$$$ строки содержат по два целых числа $$$u$$$ и $$$v$$$ $$$(1 \le u, v \le n; u \neq v)$$$  — обозначающие ребро между вершинами $$$u$$$ и $$$v$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите любую подходящую перестановку  — перестановку длины $$$n$$$, которая максимизирует количество вершин, которые Eikooc может выбрать в первый ход и иметь выиграшную стратегию. Если таких перестановок несколько, вы можете вывести любую из них.

Пример
Входные данные
3
1
2
1 2
3
1 2
1 3
Выходные данные
1
2 1
1 2 3
Примечание

В первом наборе входных данных у Eikooc есть только одна вершина. У Sushi не будет ходов после того, как Eikooc выберет эту вершину, и Eikooc выиграет.

Во втором наборе входных данных $$$1 \oplus 2 = 3 \nleq min(1, 2)$$$. Следовательно, после того, как Eikooc выберет любую из вершин, у Sushi не останется ходов, и Eikooc выиграет. И $$$\{1, 2\}$$$, и $$$\{2, 1\}$$$ являются допустимыми перенумерациями.