一只猫住在一棵有 $$$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$$$ 以及所有相邻边
示例
输入复制
451 22 31 55 421 241 21 31 461 21 33 44 54 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$$$ 处死亡。