CF2179F Blackslex and Another RGB Walking

这是一个二次运行（通讯）问题。 有两名玩家：玩家 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 将前往的邻居编号。

 图与样例中的染色方案如上图所示。 在第二次运行中，第一个测试用例有两个询问。 第一个询问在顶点 $4$，其邻居为 $6$、$2$、$7$。选择第一个邻居即走向顶点 $6$。 第二个询问在顶点 $6$，邻居为 $5$、$4$、$1$。选择第三个邻居（即走向顶点 $1$）。 第二个测试用例有一个询问，位于顶点 $2$，邻居为 $1$ 和 $4$。选择第一个邻居即走向顶点 $1$。 请注意，由于便于阅读，样例间加了空行，实际测试数据没有空行。 \[比赛时仅供参考\] 图片无法显示时的备用图片链接： 由 ChatGPT 5 翻译