A16652. Catshock
编程题
普及+/提高
知识点
题目描述
有一只猫住在一棵有 $n$ 个节点的树上。猫一开始在节点 $1$，而你在节点 $n$。你需要给猫写一封使用“跑酷”语言的留言，帮助它到达你所在的位置。
“跑酷”语言有两种指令：
- $1$ — 这意味着猫应该移动到它的任意一个相邻节点，如果有多个选择，它会随意选一个。如果没有相邻节点，它不会移动。
- $2\,u$ — 这意味着摧毁节点 $u$ 以及与其相连的所有边。如果猫当前在节点 $u$，它会死亡，所以应避免这种情况。如果节点 $u$ 已经被摧毁，则不会发生任何事情。
此外，不能有连续两条第二种指令。
可惜的是，“跑酷”语言是不明确的，因为猫每执行一次第一种指令可能会有多种选择。因此，你需要构造一个长度不超过 $3n$ 的指令序列，使得无论猫如何选择，只要按照你的指令执行，最终它一定会到达节点 $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$。
每组测试数据的第一行包含一个整数 $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$ 及其所有相邻边。
接下来输出 $k$ 行，每行可以是以下两种格式之一：
- $1$ — 让猫移动到相邻节点（如果存在）。
- $2\,u$（$1 \le u \le n$）— 删除节点 $u$ 及其所有相邻边。
输入输出样例
输入 #1
4 5 1 2 2 3 1 5 5 4 2 1 2 4 1 2 1 3 1 4 6 1 2 1 3 3 4 4 5 4 6
输出 #1
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$。
下图展示了第一组测试数据中猫的路径：
可以看出，这里猫只有这一条路径，因此它一定会到达节点 $5$。
对于第一组测试数据，以下这种指令序列是错误的：$\mathtt{1}$, $\mathtt{2}$, $\mathtt{2}$。可能出现如下情况：
此时，猫死在了节点 $2$。