Description

Ann 和她的朋友 Kathrin 最近发现了一款新桌游，这款游戏成了她们的最爱：Laser Strike。在这款游戏中，两位玩家需要协作将棋盘上的 $N$ 个棋子全部移除。游戏分为两个阶段。关键在于，Kathrin 并不了解全部信息。为了赢得游戏，Ann 和 Kathrin 必须协作，并且尽量减少交流。

棋盘上有 $N$ 个独特的棋子，编号为 $0$ 到 $N-1$。两位玩家都可以看到这些棋子。此外，棋盘上有 $N-1$ 条连接，每条连接连接一对棋子，使得任意两个棋子之间都可以通过若干条连接到达。换句话说，这些连接构成了一棵树。只有 Ann 能看到这些连接；Kathrin 并不知道它们。

在游戏的第一阶段，Ann 决定一个移除棋子的顺序 $l_0, l_1, \ldots, l_{N-2}$，直到只剩下最后一个棋子。这个顺序对 Kathrin 保密。如果 Kathrin 能复现这个顺序，两人就能赢得游戏。每次移除棋子时，需满足如下规则：每次被移除的棋子，必须与仅剩的一个棋子直接连接。换句话说，每次被移除的棋子都必须是当前剩余树中的一个叶子节点。（当 $N-1$ 个棋子都被移除后，最后一个棋子自动被移除，游戏胜利。）Ann 必须选择一个满足上述规则的移除顺序。

Ann 还会写下一条信息给 Kathrin，形式为一个二进制字符串。Ann 可以自选信息长度——信息越短，得分越高。

之后，游戏进入第二阶段。目标是让 Kathrin 按顺序 $l_0, l_1, \ldots, l_{N-2}$ 移除 $N-1$ 个棋子。她会进行 $N-1$ 步操作。在第 $i$ 步操作前，Ann 会告诉 Kathrin 一对整数 $a, b$，满足：

• $a < b$；
• 这两个棋子 $a$ 和 $b$ 之间在当前剩余棋子中有直接连接；
• $a$ 或 $b$ 中有一个就是本轮应被移除的棋子 $l_i$。

注意，对于 Ann 来说，当前树中每个叶子 $l_i$ 都能唯一确定一个连接 $(a, b)$。

然后，Kathrin 会选择移除 $a$ 或 $b$ 中的一个棋子。如果她移除的是正确的叶子 $l_i$，游戏继续；否则游戏失败。

你的任务是同时实现 Ann 和 Kathrin 的策略，使她们能够赢得游戏。

你的程序得分取决于 Ann 在第一阶段写下的信息长度。

实现细节

这是一道通信题。

本题为多轮运行题目，你的程序会被执行两次。第一次运行时，实现 Ann 的策略（第一阶段）；第二次运行时，实现 Kathrin 的策略（第二阶段）。

输入的第一行包含两个整数 $P$ 和 $N$，其中 $P$ 为 1 或 2（分别表示第一或第二阶段），$N$ 为棋子数量。

后续输入内容取决于阶段：

阶段 1：Ann

第一行后，接下来 $N-1$ 行描述树的结构。每行两个整数 $a$ 和 $b$（$0 \leq a < b \leq N-1$），表示棋子 $a$ 和 $b$ 之间有一条连接。

你的程序应首先输出一个二进制字符串（长度不超过 1000），即 Ann 写给 Kathrin 的信息。若信息长度为 0，输出空行。

然后输出 $N-1$ 个整数 $\ell_0, \ell_1, \ldots, \ell_{N-2}$，每行一个，表示 Ann 希望的叶子移除顺序。该顺序必须满足每次移除的都是当前树的叶子。

阶段 2：Kathrin

第一行后，下一行输入为 Ann 的二进制信息。

接下来有 $N-1$ 轮交互，每轮代表 Kathrin 的一次操作。

在第 $i$ 轮，你的程序应首先读入两个整数 $a$ 和 $b$（$0 \leq a < b \leq N-1$）。其中一个是当前应移除的叶子 $\ell_i$，另一个是唯一与其直接连接的剩余棋子。然后，你的程序应输出 $\ell_i$，即 Kathrin 选择移除该叶子。如果输出不是正确的叶子，游戏失败，本测试点判为 Wrong Answer。

细节说明

两次运行的总时间不得超过时限，否则会被判为 TLE。

每次输出后请及时刷新标准输出，否则可能被判为 TLE。Python 用 input() 读入时自动刷新；C++ 可用 cout << endl; 或 fflush(stdout);。

注意，正确读取空字符串可能有点棘手。官方模板已正确处理此情况。

Input Format

见实现细节。

Output Format

见实现细节。

1 7
0 1
1 2
2 3
0 4
0 6
1 5

0110
5
3
2
6
4
0

2 7
0110
1 5

2 3

1 2

0 6

0 4

0 1

5

3

2

6

4

0

Hint

样例说明

注意，以下样例 $N=7$，仅为说明方便，并非正式测试用例。正式评测所有用例均有 $N=1000$。

在样例中，Ann 得到如下树结构。在第一阶段，Ann 读入树，选择二进制串 "0110" 发送给 Kathrin，并选择移除顺序 $[\ell_0, \ell_1, \ldots, \ell_{N-2}] = [5, 3, 2, 6, 4, 0]$。第二阶段，Kathrin 收到 Ann 的二进制串 "0110"，随后收到对 $(1,5)$ 并选择移除 5，接着收到对 $(2,3)$ 并移除 3，依此类推。下图展示了交互过程：

测试工具

为方便测试，官方提供了一个简单的工具。见 Kattis 题目页面底部的“attachments”。该工具可选，正式评测器与该工具不同。

用法：准备一个输入文件（如 "sample1.in"），文件第一行为 $N$，接下来 $N-1$ 行描述树结构，格式同阶段 1。例如：

7
0 1
1 2
2 3
0 4
0 6
1 5

对于 Python 程序（如 solution.py，通常用 pypy3 solution.py 运行），可用如下命令：

python3 testing_tool.py pypy3 solution.py < sample1.in

C++ 程序编译后（如 g++ -g -O2 -std=gnu++23 -static solution.cpp -o solution.out），可用如下命令：

python3 testing_tool.py ./solution.out < sample1.in

约束与评分

• $N = 1000$
• 对所有连接，$0 \leq a < b \leq N-1$

你的解答将在一组测试组上进行评测，每组包含若干测试用例。要获得该测试组分数，你需要通过该组所有测试用例。

组别	满分	限制
1	8	树为星形，即除一个节点外其余全为叶子
2	9	树为链形，即除两个叶子外其余每个节点度数为 2
3	21	树为“星形加链”，即所有节点度为 1 或 2，只有一个节点度大于 2
4	36	任意两点间距离不超过 10
5	26	无额外限制

对于每个通过的测试组，你的得分按下式计算：

$$\text{score} = S_g \cdot (1 - 0.3 \cdot \log_{10} \max(K, 1))$$

其中 $S_g$ 为该测试组满分，$K$ 为该组任一测试用例中 Ann 的消息最大长度。每组得分四舍五入取整。

下表给出若干 $K$ 时的总分示例，若所有测试组都通过且 $K$ 如下：

$K$	1	5	10	50	100	500	1000
得分	100	79	70	49	39	20	11

翻译由 ChatGPT-4.1 完成。