CF2154D.Catshock

A cat lives on a tree with $n$ nodes. The cat starts on node $1$, and you live on node $n$. You are going to leave the cat a note written in the parkour language to help it reach you.

The parkour language has two types of instructions:

• $1$ — This means that the cat should move to any adjacent node to it, if there are multiple options, it will pick one of them arbitrarily. If there are no adjacent nodes to it, then it will not move.
• $2\,u$ — This means to destroy node $u$ and all adjacent edges to it. If the cat is currently on node $u$, it will die, so this should be avoided. If node $u$ was already destroyed, then nothing will happen.

Additionally, there cannot be two consecutive instances of the second instruction.

Unfortunately, the parkour language is ambiguous because the cat may have multiple options for each instance of the first instruction. So you should construct a sequence of instructions of length at most $3n$ so that if the cat follows them, it will end at node $n$, no matter what choices it makes. It can be proven that such a sequence exists for any tree.

一只猫生活在一棵有 $n$ 个节点的树上。猫起始于节点 $1$，而你住在节点 $n$。你打算在公园跑酷语言（parkour language）中写一张纸条留给猫，以帮助它抵达你所在的位置。

公园跑酷语言包含两种指令：

• $1$ — 表示猫应移动到其任意一个相邻节点；若存在多个相邻节点，则猫可任意选择其中一个；若不存在相邻节点，则猫不移动。
• $2\,u$ — 表示摧毁节点 $u$ 及其所有邻接边。若猫当前正位于节点 $u$ 上，则它会死亡，因此必须避免这种情况。若节点 $u$ 已被摧毁，则该指令不产生任何效果。

此外，不允许连续出现两次第二种指令（即形如 $2\,u$ 的指令）。

不幸的是，公园跑酷语言具有歧义性，因为每次执行第一种指令（即 $1$）时，猫可能有多种移动选择。因此，你需要构造一个长度至多为 $3n$ 的指令序列，使得：无论猫在每次执行指令 $1$ 时如何选择相邻节点，它最终都必定停在节点 $n$ 上。可以证明：对任意一棵树，这样的指令序列均存在。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each testcase contains an integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the size of the tree.

Then $n - 1$ lines follow, each of them contains two integers $u$ and $v$ ($1 \le u,v \le n, u \ne v$) which describe a pair of vertices connected by an edge. It is guaranteed that the given graph is a tree and has no loops or multiple edges.

The sum of $n$ across all testcases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each testcase, output a single integer $k$ ($0 \le k \le 3n$) — the number of operations you will perform.

Then output $k$ lines of either of the following formats:

• $1$ — make the cat move to an adjacent node if there are nodes adjacent to it.
• $2\,u$ ($1 \le u \le n$) — delete node $u$ along with all adjacent edges

对于每个测试用例，输出一个整数 $k$（$0 \le k \le 3n$）—— 表示你将执行的操作次数。

然后输出 $k$ 行，每行格式为以下两种之一：

• $1$ — 若猫当前所在节点存在相邻节点，则令猫移动到其中一个相邻节点；
• $2\,u$（$1 \le u \le n$）— 删除节点 $u$ 及其所有关联的边。

There are extra spaces between the output of different test cases only for clarity, and the participants are not expected to print them.

The path of the cat in the first testcase is shown below.

It can be shown that this is the only possible path, and so the cat will always end at node $5$.

An example of a sequence of instructions that does not work for the first testcase is: $\mathtt{1}$, $\mathtt{2}$ $\mathtt{2}$. As the following may happen:

Here the cat died at node $2$.

不同测试用例的输出之间额外添加的空格仅为了便于阅读，参赛者无需输出这些空格。

第一个测试用例中猫的路径如下所示：

可以证明这是唯一可能的路径，因此猫最终必定停在节点 $5$。

第一个测试用例中一个无效的指令序列示例如下：$\mathtt{1}$、$\mathtt{2}$、$\mathtt{2}$。此时可能发生如下情况：

此时猫在节点 $2$ 处死亡。