You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

这是一道通信题。在本题中，你的程序将运行两次。两次运行之间，内存中存储的所有变量都将丢失，但 第一次运行中获取的信息可能对第二次运行中正确解决问题非常重要。

本题中有 “奶龙” 和 “暴暴龙” 两个角色。 奶龙拥有一棵包含 $n$ 个节点的树^[1]的完整结构信息，而暴暴龙只知道树的节点数 $n$。由于暴暴龙被邪恶的小豹子关起来了，所以奶龙只能通过一种特殊的单向通信方式，来帮助暴暴龙还原出一棵与原树同构^[2]的树。

通信的规则如下：

• 奶龙需要给树上的每个节点染色为黑色或者白色。

• 小豹子会按如下代码生成一个序列：

• 奶龙只能把这个长为 $2n-1$ 的序列 $c_1, c_2, \dots, c_{2n-1}$ 发送给暴暴龙。

奶龙无法直接将节点编号发给暴暴龙，她只能将序列 $c$ 发送给暴暴龙。暴暴龙在收到 $n$ 以及序列 $c$ 后，需要构造并输出一棵与奶龙的树同构的树。

通信方式

每个测试点中，选手程序将被运行两次。在下发文件中，提供了一份测试工具供选手本地调试使用。

第一次运行

在第一次运行中，你将扮演 “奶龙” 角色。

输入格式

输入的第一行包含一个字符串 first，其作用是让你的程序能够识别这是第一次运行。

第二行包含一个整数 $T(1 \le T \le 10^4)$, 表示数据组数.

对于每组数据：

• 第一行包含一个整数 $n(2 \le n \le 2 \times 10^5)$，表示树的节点数。

• 接下来 $n − 1$ 行，每行包含两个整数 $u, v (1 \le u, v \le n)$，表示树上的一条边。

数据保证 $n$ 的和不超过 $2 \times 10^5$。

输出格式

你的输出应该包含 $T$ 行, 第 $i$ 行包含一个长度与第 $i$ 棵树节点数量 $n$ 相同的序列 $col_1, col_2, \dots, col_n(col_i \in \{0, 1\}, i = 1, 2, \dots, n)$ 表示奶龙给第 $i$ 个节点染色为 $col_i$. $col_i = 0$ 为白色, $col_i = 1$ 为黑色.

第二次运行

在第二次运行中，你将扮演 “暴暴龙” 角色。

输入格式

输入的第一行包含一个字符串 second，其作用是让你的程序能够识别这是第二次运行。

第二行包含一个整数 $T(1 \le T \le 10^4)$, 表示数据组数.

对于每组数据：

• 第一行包含一个整数 $n (2 \le n \le 2 \times 10^5)$, 分别表示节点数。

• 接下来一行 $2n - 1$ 个整数, 表示评测机根据奶龙的染色生成的序列.

数据保证 $n$ 的和不超过 $2 \times 10^5$。

输出格式

对于每第 $i$ 组数据, 设输入节点数为 $n$, 则输出 $n - 1$ 行, 每行两个整数 $u, v$, 表示你还原出的树的一条边 $(1 \le u, v \le n)$. 你需要保证输出的树和第一次运行中输入的树同构.

样例

第一次运行

first
2
2
1 2
3
1 2
2 3

0 1
0 1 0

第二次运行

second
2
3
0 1 0 1 0
2
0 1 0

1 3
2 3
1 2

样例说明

两个样例演示了同一测试点中的两次运行。

注意, 如果第一次输入的树依次为 $t_1, \dots, t_T$, 输出的颜色序列为 $col_1, \dots, col_T$. 设评测器根据 $t_i, col_i (1 \le i \le T)$ 得到的颜色序列为 $a_i$, 评测器会随机生成一个 $1 \sim T$ 的排列 $p_1, \dots, p_T$, 然后评测器发送到第二次输入的顺序为 $a_{p_1}, \dots, a_{p_T}$, 输出的树依次为 $t'_1, t'_2, \dots, t'_T$, 评测器会将 $t_{p_i}$ 与 $t_i'$ 比较进行评测.

下发文件使用方法

python3 tree_communication_testing_tool2.py data.in ./solution
python3 tree_communication_testing_tool2.py --trials 10 data.in ./solution
python3 tree_communication_testing_tool2.py data.in python3 solution.py

其中 solution 或 solution.py 为 C/C++ 编译出的可执行文件或 python 源码, data.in 为第一次输入的数据, trials 参数表示该重复测试的次数。