← 返回题目列表

Codeforces · 2133/E

E. 我渴望矿井

中文机器翻译题面 查看原题

作为一个孩子,史蒂夫向往地雷!他的矿可以表示为一棵由 $$$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$$$。

示例

输入
复制

2
2
1 2
4
1 2
2 3
4 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$$$ 操作中的这三个节点后,他肯定已被捕获。