题目描述

这是一个二次运行（通讯）问题。

有两名玩家：玩家 A（Agent，特工）和玩家 B（Blackslex）。评测机会先与玩家 A 交互。在玩家 A 结束交互后，评测机会与玩家 B 交互。注意，玩家 A 和玩家 B 不能直接传递信息；他们只能向评测机发送或从评测机接收信息，但可以事先约定通信策略。

企鹅共和国是一个连通的无向二分图 $G$，有 $n$ 个顶点和 $m$ 条边。Blackslex 将在顶点 $1$ 进行违禁野外研究。由于旅行限制，他将被随机送往一个未知顶点 $v$（$2 \leq v \leq n$）。他必须设法到达顶点 $1$，但他对图结构一无所知。

为完成任务，他贿赂了一名企鹅特工，并提前约定了如下通信方式：特工将每个顶点涂成三种颜色之一：红色（r）、绿色（g）、蓝色（b）。对 Blackslex 来说，他只能看到他所在顶点 $v$ 的每个邻居 $u_i$（$1 \leq i \leq d(v)$）的颜色 $c_i$。之后，他必须选择某一个 $j$（$1 \leq j \leq d(v)$），并前往顶点 $u_j$，使得他离顶点 $1$ 更近。

邻居顺序是任意排列的。他只能看到周围邻居的颜色，无法得知自己当前所处的顶点编号；同样他也不知道相邻顶点的编号或任意其他顶点的信息。

你的任务是为特工和 Blackslex 分别实现策略。对于特工，需要将每个顶点染成三种颜色之一。对于 Blackslex，在每次询问中，他被随机放置在某个未知顶点 $v$，并给出所有邻居当前的颜色，你需要确定应前往哪一个邻居 $u_j$，使他能朝顶点 $1$ 前进。

$^*$ $d(v)$ 表示顶点 $v$ 的邻居数量。

输入格式

你的代码将在每组测试中被精确运行两次。第一次运行时你作为玩家 A（Agent），第二次运行时你作为玩家 B（Blackslex）。

第一次运行输入

第一行输入字符串 first，用于让你的程序判断这是第一次运行，应作为 Agent 角色。

每组测试包含多个测试用例。第一行输入一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例数量。

每个测试用例的第一行输入两个整数 $n$ 和 $m$（$2 \leq n \leq 10^5$，$n-1 \leq m \leq 10^5$），分别表示顶点数和边数。

接下来 $m$ 行每行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$），表示顶点 $a_i$ 与顶点 $b_i$ 之间有一条边。

保证以下条件：

• 所有测试用例中 $n$ 之和与 $m$ 之和均不超过 $10^5$。
• 每个测试用例的图都是连通的、无重边和自环的二分图。

第二次运行输入

第一行输入字符串 second，用于让你的程序判断这是第二次运行，应作为 Blackslex 角色。

每组测试包含多个测试用例。第一行输入整数 $t$（$1 \leq t \leq 10^4$），与第一次运行输入的 $t$ 相同。每个测试用例的描述如下。

第一行输入一个整数 $q$（$1 \leq q \leq 10^5$），表示本测试用例中的询问数。

每个询问的第一行输入一个整数 $d(v)$（$1 \leq d(v) \leq 10^5$），表示当前顶点 $v$ 的邻居数量。

接下来一行输入一个长度为 $d(v)$ 的字符串 $c$，表示所有邻居的颜色，第 $i$ 位（$1 \leq i \leq d(v)$）为邻居 $u_i$ 的颜色，可能为 r（红）、g（绿）、b（蓝）。

保证以下条件：

• 所有测试用例中 $q$ 之和不超过 $10^5$。
• 所有测试用例中 $d(v)$ 之和不超过 $2 \cdot 10^5$。
• $v \neq 1$。

第二次运行输入是非自适应的，即不会因你的程序输出而改变。

Hack 数据

构造 Hack 时，请使用如下输入格式：

第一行输入整数 $t$（$1 \leq t \leq 10^4$），表示测试用例数量。

接下来是每组测试用例的第一次运行描述：

每个测试用例第一行输入两个整数 $n$ 和 $m$（$2 \leq n \leq 10^5$，$n-1 \leq m \leq 10^5$），描述图。

接下来 $m$ 行每行输入两个整数 $a_i$ 和 $b_i$，表示有一条 $a_i$ 到 $b_i$ 的边。

然后是每个测试用例第二次运行的描述：

每个测试用例的第一行输入一个整数 $q$（$1 \leq q \leq 10^5$），为该用例中询问数量。

每个询问的第一行输入一个整数 $v$（$2 \leq v \leq n$），表示 Blackslex 被放置的顶点编号。

每个询问第二行输入 $d(v)$ 个整数 $p_1, p_2, \ldots, p_{d(v)}$（$1 \leq p_i \leq d(v)$，且 $p$ 中每个数各不相同），表示邻居的排列顺序。设 $q_1 < q_2 < \ldots < q_{d(v)}$ 为 $v$ 的所有邻居，输入序中第 $i$ 个邻居为 $u_i = q_{p_i}$。

必须保证如下条件：

• 所有测试用例第一次运行中 $n$ 和 $m$ 之和均不超过 $10^5$。
• 每个测试用例图是连通、无重边且为二分图。
• 所有测试用例二次运行询问中 $q$ 之和不超过 $10^5$。
• 所有测试用例 $d(v)$ 总和不超过 $2 \cdot 10^5$。

输出格式

对于第一次运行的每个测试用例，输出一个字符串 $s$，长度为 $n$，其中 $s_i$（$1 \leq i \leq n$）为你给第 $i$ 个顶点染的颜色。每个字符只能为 r（红）、g（绿）、b（蓝）。

对于第二次运行的每个测试用例中每个询问，输出一个整数 $j$（$1 \leq j \leq d(v)$），$u_j$ 为 Blackslex 将前往的邻居编号。

样例

first
2
7 8
1 2
1 6
3 2
4 2
6 4
4 7
5 6
5 7

4 4
1 2
1 3
4 2
4 3

rrgbggr
rbbb

second
2
2
3
grr
3
gbr

1
2
rb

1
3
1

样例说明

图与样例中的染色方案如上图所示。

在第二次运行中，第一个测试用例有两个询问。

第一个询问在顶点 $4$，其邻居为 $6$、$2$、$7$。选择第一个邻居即走向顶点 $6$。

第二个询问在顶点 $6$，邻居为 $5$、$4$、$1$。选择第三个邻居（即走向顶点 $1$）。

第二个测试用例有一个询问，位于顶点 $2$，邻居为 $1$ 和 $4$。选择第一个邻居即走向顶点 $1$。

请注意，由于便于阅读，样例间加了空行，实际测试数据没有空行。

[比赛时仅供参考] 图片无法显示时的备用图片链接：https://ibb.co/yFZS16vj

由 ChatGPT 5 翻译

来源

Codeforces 2179F，英文题名 Blackslex and Another RGB Walking。