A16652 · Catshock · GESP考级

题目描述

有一只猫住在一棵有 $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$ 及其所有相邻边。

输入 #1

输出 #1