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

Кошка живет на дереве с $$$n$$$ вершинами. Сейчас кошка находится на вершине $$$1$$$, а вы живете на вершине $$$n$$$. Вы собираетесь оставить кошке записку, написанную на языке паркура, чтобы помочь ей добраться до вас.

Язык паркура имеет два типа инструкций:

  • $$$1$$$ — кошка должна переместиться на любую соседнюю вершину. Если есть несколько вариантов, она выберет один из них произвольно. Если соседних вершин нет, она не будет двигаться.
  • $$$2\,u$$$ — уничтожить вершину $$$u$$$ и все её рёбра. Если кошка в данный момент находится на вершине $$$u$$$, она погибнет, поэтому этого следует избегать. Если вершина $$$u$$$ уже была уничтожена, то ничего не произойдет.

Кроме того, не может быть двух последовательных применений второй инструкции.

К сожалению, язык паркура неоднозначен, потому что у кошки может быть несколько вариантов для каждого случая первой инструкции. Поэтому вам нужно построить последовательность инструкций длиной не более $$$3n$$$, так чтобы, если кошка будет следовать им, она в конечном итоге окажется на вершине $$$n$$$, независимо от того, какие выборы она сделает. Можно доказать, что такая последовательность существует для любого дерева.

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

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

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

Затем следуют $$$n - 1$$$ строк, каждая из которых содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u,v \le n, u \ne v$$$), которые описывают пару вершин, соединённых ребром. Гарантируется, что данный граф является деревом и не имеет петель или кратных рёбер.

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

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

Для каждого набора входных данных выведите одно целое число $$$k$$$ ($$$0 \le k \le 3n$$$) — количество операций, которые вы выполните.

Затем выведите $$$k$$$ строк в одном из следующих форматов:

  • $$$1$$$ — заставьте кошку переместиться на соседнюю вершину, если такие вершины есть.
  • $$$2\,u$$$ ($$$1 \le u \le n$$$) — удалите вершину $$$u$$$ вместе со всеми соседними рёбрами
Пример
Входные данные
4
5
1 2
2 3
1 5
5 4
2
1 2
4
1 2
1 3
1 4
6
1 2
1 3
3 4
4 5
4 6
Выходные данные
2
2 2
1

1
1

5
2 2
1
1
2 3
1

9
2 2
1
2 1
1
2 3
1
1
2 5
1
Примечание

Дополнительные пробелы между результатами различных наборов входных данных добавлены исключительно для наглядности, и от участников не требуется их печатать.

Путь кошки в первом наборе входных данных показан ниже.

Можно показать, что это единственный возможный путь, и поэтому кошка всегда окажется на вершине $$$5$$$.

Пример последовательности инструкций, которая не работает для первого набора входных данных: $$$\mathtt{1}$$$, $$$\mathtt{2}$$$ $$$\mathtt{2}$$$. Так как может произойти следующее:

Здесь кошка погибла на вершине $$$2$$$.