CF2133E.I Yearned For The Mines

小时候，Steve 渴望进入矿井！他的矿井可以表示为一棵有 $n$ 个节点的树$^{\ast}$。

不幸的是，Steve 的最大死敌 Herobrine 潜入了他的矿井！任何时刻，Herobrine 都正好藏在一个节点里；最初，他可能在任意一个节点。Steve 可以执行以下操作：

• $1\,\,x$ —— 检查 Herobrine 当前是否在节点 $x$。如果在，Steve 就抓住了他。否则，Herobrine 可以选择是否移动到任意一个相邻节点（除了你刚刚检查过的那个）。
• $2\,\,x$ —— 摧毁所有与节点 $x$ 相连的边；Herobrine 之后将无法再通过这些边移动。随后，Herobrine 可以选择是否移动到任意一个相邻节点。

请你找出一组不超过 $\left\lfloor \frac{5}{4} \cdot n \right\rfloor$ 次操作的方案，使得无论 Herobrine 最初藏在哪里、如何移动，Steve 都一定能抓住他。我们已经证明，在给定约束下总是存在这样的方案。

$^{\ast}$树是一个无环连通图。

每个测试点包含多组测试数据。第一行包含一个整数 $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$ 次操作是在节点 $x_i$ 上执行操作 $t_i$。

在第一个测试点中，树的结构如下：

最初，Herobrine 可能在任意一个节点。第一次操作检查节点 $1$，如果 Herobrine 在节点 $1$，他就被抓住了；否则，他只能在节点 $2$（他不能移动到刚刚检查过的节点 $1$）。因此，第二次操作检查节点 $2$，Herobrine 必然被抓住。

在第二个测试点中，树的结构如下：

最初，Herobrine 可能在任意一个节点 $[1, 2, 3, 4]$。第一次操作后，Herobrine 只能在节点 $[1, 3, 4]$。第二次操作摧毁了与节点 $2$ 相连的所有边。由于与节点 $1$、$3$、$4$ 相连的所有边都被摧毁，Herobrine 无法再移动。因此，接下来分别检查这三个节点（操作 $3$、$4$、$5$），就一定能抓住 Herobrine。

由 ChatGPT 4.1 翻译