D. Обход яблони
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Существует яблоневое дерево с $$$n$$$ вершинами, изначально на каждой вершине находится одно яблоко. У вас есть бумага, на которой изначально ничего не написано.

Вы обходите яблоневое дерево, выполняя следующие действия, пока на ней остаётся хотя бы одно яблоко:

  • Выберите яблочный путь $$$(u,v)$$$. Путь $$$(u,v)$$$ называется яблочным путём, если и только если на каждой вершине на пути $$$(u,v)$$$ есть яблоко.
  • Пусть $$$d$$$ — это количество яблок на пути. Запишите три числа $$$(d,u,v)$$$ в этом порядке на бумаге.
  • Затем удалите все яблоки на пути $$$(u,v)$$$.

Здесь путь $$$(u, v)$$$ обозначает последовательность вершин на единственном кратчайшем пути от $$$u$$$ до $$$v$$$.

Пусть в результате на бумаге была записана последовательность чисел $$$a$$$. Ваша задача — найти лексикографически наибольшую возможную последовательность $$$a$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

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

Следующие $$$n-1$$$ строк каждого набора входных данных содержат два числа $$$u,v$$$ ($$$1 \le u,v \le n$$$). Гарантируется, что входные рёбра образуют дерево.

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

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

Для каждого набора входных данных выведите лексикографически наибольшую возможную последовательность $$$a_1, a_2, \ldots, a_{|a|}$$$. Можно показать, что $$$|a| \le 3 \cdot n$$$.

Пример
Входные данные
6
4
1 2
1 3
1 4
4
2 1
2 4
2 3
5
1 2
2 3
3 4
4 5
1
8
6 3
3 5
5 4
4 2
5 1
1 8
3 7
6
3 2
2 6
2 5
5 4
4 1
Выходные данные
3 4 3 1 2 2 
3 4 3 1 1 1 
5 5 1 
1 1 1 
5 8 7 2 4 2 1 6 6 
5 6 1 1 3 3
Примечание

В первом наборе входных данных можно выполнить следующие шаги:

  • Выбрать яблочный путь $$$(4, 3)$$$. Этот путь состоит из вершин $$$4, 1, 3$$$, и на каждой из них есть яблоко (так что это действительно яблочный путь). $$$d = 3$$$, так как на этом пути $$$3$$$ яблока. Добавить $$$3, 4, 3$$$ в таком порядке в нашу последовательность $$$a$$$. Далее удалить яблоки с этих $$$3$$$ вершин.
  • Осталось только яблоко на вершине $$$2$$$. Выбрать яблочный путь $$$(2, 2)$$$. Этот путь состоит только из одной вершины $$$2$$$. $$$d = 1$$$, так как на этом пути $$$1$$$ яблоко. Добавить $$$1, 2, 2$$$ в таком порядке в нашу последовательность $$$a$$$ и удалить яблоко с вершины $$$2$$$.

Таким образом, конечная последовательность будет $$$[3, 4, 3, 1, 2, 2]$$$. Можно показать, что это лексикографически наибольшая возможная последовательность.