← 返回题目列表

Codeforces · 1879/E

E. 填色互动游戏

中文机器翻译题面 查看原题

这是一个交互问题。请记住在与测试程序通信时刷新输出。您可以在 C++ 中使用 fflush(stdout)、Java 中的 system.out.flush()、Python 中的 stdout.flush() 或 Pascal 中的lush(output) 来刷新输出。如果您使用其他编程语言,请查阅其文档。您还可以参考交互问题指南:https://codeforces.com/blog/entry/45307。

给你一棵有 $$$n$$$ 个顶点的树;顶点 $$$1$$$ 是树的根。对于 [2, n]$$$ 中的每个 $$$i \in,第 $$$i$$$ 个顶点的父顶点是 $$$p_i$$$,且 $$$p_i < i$$$。

您必须使用尽可能少的颜色为树的所有边缘着色,这样您才能赢得该树上的游戏(每个边缘都应该涂成一种颜色)。

我们要玩的游戏将按如下方式进行。绘制边缘并打印颜色后,评审团会将芯片放入树的一个顶点(根部除外)。您的目标是在 $$$d$$$ 移动中将此芯片移至根部,其中 $$$d$$$ 是从根部到该顶点的距离(该距离等于路径上的边数)。如果筹码在 $$$d$$$ 步中到达根部,您就赢了。否则,你就输了。

陪审团不会告诉您芯片所在的位置。您甚至不会提前知道 $$$d$$$ 的价值。但是,在每次移动开始时,您将被告知每种颜色有多少条边与当前顶点相关(这包括通向树的边和远离根的边)。您必须选择这些颜色中的一种,并且芯片将沿着所选颜色的边缘移动(如果有多个边缘与当前顶点相关的颜色,陪审团可以选择其中之一)。移动筹码后,您将再次被告知有关当前顶点的相同信息,并且游戏继续,直到您到达根部,或者您进行 $$$d$$$ 移动但未到达根部。

这个问题的交互器是自适应的。这意味着起始顶点和当前顶点都不是固定的,并且可能会根据程序的输出“在运行时”发生变化。然而,游戏的状态将始终与您所获得的信息一致:始终存在至少一个起始顶点,并且从该顶点出发的筹码的至少一条路径与您收到的颜色信息和您在移动过程中选择的颜色一致。

输入

第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 100$$$) — 树中的顶点数。

第二行包含 $$$n-1$$$ 整数 $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i < i$$$),其中 $$$p_i$$$ 是树中第 $$$i$$$ 个顶点的父顶点。

互动

首先,您必须打印所选边缘的颜色,如下所示:

- 在第一行中,打印一个整数 $$$k$$$ ($$$1 \le k \le n - 1$$$) — 您正在使用的颜色数量;
- 在第二行中,打印 $$$n-1$$$ 整数 $$$c_2, c_3, \dots, c_n$$$ ($$$1 \le c_i \le k$$$),其中 $$$c_i$$$ 应该是连接 $$$p_i$$$ 与 $$$i$$$ 的边的颜色。

然后,游戏开始。在每一步开始时,陪审团程序都会打印以下内容之一:

- 一个整数 $$$1$$$ 独占一行,表示筹码已经到达根部,你赢了;
- 一个整数 $$$-1$$$ 位于单独的一行,表示您在 $$$d$$$ 步中没有到达根部并失败,或者您做了一些不正确的事情(您提供的颜色不符合约束,或者您之前的移动是不可能的);
- 或单独一行上的一个整数 $$$0$$$,后跟一行包含 $$$k$$$ 整数 $$$e_1, e_2, \dots, e_k$$$,其中 $$$e_i$$$ 是与当前顶点相关的颜色 $$$i$$$ 的边数。

如果您收到 $$$1$$$ 或 $$$-1$$$,您的程序应立即终止,否则您提交的结论可能不确定。如果您收到 $$$0$$$ 后跟 $$$k$$$ 整数 $$$e_1, e_2, \dots, e_k$$$,则必须打印一个整数来指示您在移动过程中选择的颜色(当然,该颜色的 $$$e_i$$$ 不应等于 $$$0$$$)。

每次打印内容时不要忘记刷新输出!

示例

输入 #1

5
1 1 1 1
0
1
1

输出 #1

1
1 1 1 1
1

输入 #2

4
1 2 3
0
0 1 0
0
1 1 0
0
1 0 1
1

输出 #2

3
3 1 2
2
1
3

输入 #3

3
1 2
0
1 1
1

输出 #3

2
1 2
1

注意

在第一个示例中,从 $$$2$$$ 到 $$$n$$$ 的每个顶点都连接到根。因此,我们可以将所有边绘制为相同的颜色$$$1$$$,并且当游戏开始时,只有一条边与当前顶点相关(并且它将通向根)。

在第二个示例中,树是 $$$4$$$ 个顶点的路径。我们必须将其边缘涂成不同的颜色,因为这可以表明我们没有仅用两种颜色的获胜策略。