作为一个孩子,史蒂夫向往地雷!他的矿可以表示为一棵由 $$$n$$$ 节点组成的树$$$^{\text{*}}$$$。
不幸的是,史蒂夫的矿井已经被他最大的宿敌 Herobrine 渗透了!在任何时候,Herobrine 都恰好隐藏在一个节点中;最初,他可能属于其中任何一个。 Steve 可以执行以下操作:
- $$$1\,\,x$$$ — 检查 Herobrine 当前是否位于节点 $$$x$$$ 中。如果他是,史蒂夫就会抓住他。否则,Herobrine 可能会也可能不会移动到任何相邻节点(除了 您刚刚检查的那个)。
- $$$2\,\,x$$$ — 销毁连接到节点 $$$x$$$ 的所有边; Herobrine 将无法再使用它们。之后,Herobrine 可能会也可能不会移动到任何相邻节点。
找到最多 $$$\left\lfloor \frac{5}{4} \cdot n \right\rfloor$$$ 操作的序列,以保证 Steve 抓住 Herobrine,无论 Herobrine 的初始位置和移动方式如何。我们有证据表明,在给定的约束下,这总是可能的。
$$$^{\text{*}}$$$树是没有环的连通图。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$ 和 $$$v$$$ 之间的边。
保证给定的边形成一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,首先输出一个整数 $$$k$$$ ($$$1 \le k \le \left\lfloor \frac{5}{4} \cdot n \right\rfloor$$$) - 您希望执行的操作数。
然后输出 $$$k$$$ 行。 $$$i$$$ ($$$1 \le i \le k$$$) 行应包含两个整数 $$$t_i$$$ 和 $$$x_i$$$ ($$$1 \le t_i \le 2$$$, $$$1 \le x_i \le n$$$),表示您希望执行的第 $$$i$$$ 操作是节点上的操作 $$$t_i$$$ $$$x_i$$$。
示例
输入复制
221 241 22 34 2
输出复制
2 1 1 1 2 5 1 2 2 2 1 1 1 3 1 4
注意
第一个测试用例中,树如下:
最初,Herobrine 可能位于任一节点中。在第一个操作检查节点 $$$1$$$ 后,如果 Herobrine 在节点 $$$1$$$ 中,他就会被抓住,因此操作后他唯一可能位于的节点是节点 $$$2$$$ (他无法移动到节点 $$$1$$$,因为它刚刚被检查)。因此,在第二次检查节点 $$$2$$$ 的操作之后,他一定已经被抓住了。
在第二个测试用例中,树如下:
最初,Herobrine 可能位于任意节点 $$$[1, 2, 3, 4]$$$ 中。第一次操作后,Herobrine 只能位于节点 $$$[1, 3, 4]$$$ 中。第二个操作破坏与节点 $$$2$$$ 相邻的所有边。由于连接到节点 $$$1$$$、$$$3$$$ 和 $$$4$$$ 的所有边现已被破坏,Herobrine 无论位于何处都无法再移动。因此,在检查 $$$3$$$、$$$4$$$ 和 $$$5$$$ 操作中的这三个节点后,他肯定已被捕获。