当前没有测试数据。

F. Blackslex and Another RGB Walking

题目描述

这是一道两次运行（通信类）交互题。

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

企鹅共和国的地图是一个二分图连通无向图 G，包含 n 个顶点和 m 条边。Blackslex 要在顶点 1 进行禁域研究，但由于旅行限制，他会被随机投放到某个未知顶点 v（2≤v≤n）。他必须在完全不了解图结构的情况下到达顶点 1。

为了完成旅程，他贿赂了一名企鹅特工，并约定了如下通信策略：特工将秘密地把每个顶点染成三种颜色之一：红色（r）、绿色（g）或蓝色（b）。从 Blackslex 的视角来看，他只能看到当前所在顶点 v 的每个邻居 u_i（1≤i≤d(v)，d(v) 表示 v 的邻居数量）的颜色 c_i。他必须选择某个 j（1≤j≤d(v)），移动到顶点 u_j，且该移动必须使他离顶点 1 更近。

注意：邻居的顺序是任意的。Blackslex 只能看到邻居的颜色，看不到自己所在的顶点；他也不知道自己所在顶点的编号、邻居的编号或其他任何顶点的信息。

你的任务是为特工和 Blackslex 实现策略：

• 对于特工（玩家 A）：需要将每个顶点染成三种颜色之一。
• 对于 Blackslex（玩家 B）：会收到 q 个查询。每个查询中，你会被投放到某个任意且未知的顶点 v，并获得该顶点所有邻居的颜色。你需要确定一个要移动到的邻居，使得移动后离顶点 1 更近。

输入格式

你的程序会在每个测试点上恰好运行两次：

• 第一次运行：你是玩家 A（特工），输入第一行为字符串 "first"。
• 第二次运行：你是玩家 B（Blackslex），输入第一行为字符串 "second"。

第一次运行（玩家 A）输入

第一行包含字符串 "first"。 接下来有 t 组测试用例（1≤t≤1e4）。 每组测试用例的第一行包含两个整数 n 和 m（2≤n≤1e5，n-1≤m≤1e5），分别表示顶点数和边数。 接下来 m 行，每行包含两个整数 a_i 和 b_i（1≤a_i,b_i≤n，a_i≠b_i），表示顶点 a_i 和 b_i 之间有一条边。

数据保证：

• 所有测试用例的 n 之和与 m 之和均不超过 1e5。
• 每组测试用例的图是二分图、连通的，无重边和自环。

第二次运行（玩家 B）输入

第一行包含字符串 "second"。 接下来有 t 组测试用例（与第一次运行的 t 相同）。 每组测试用例的第一行包含一个整数 q（1≤q≤1e5），表示该测试用例的查询数。 每个查询的第一行包含一个整数 d(v)（1≤d(v)≤1e5），表示当前所在顶点 v 的邻居数量。 每个查询的第二行包含一个长度为 d(v) 的字符串 c，其中第 i 个字符（1≤i≤d(v)）表示邻居 u_i 的颜色（r/g/b 分别代表红/绿/蓝）。

数据保证：

• 所有测试用例的 q 之和不超过 1e5。
• 所有测试用例的 d(v) 之和不超过 2e5。
• 每个查询中的 v≠1。
• 第二次运行的输入是非自适应的（即不同运行中，第二次运行的输入不会改变）。

输出格式

第一次运行（玩家 A）输出

对于每组测试用例，输出一个长度为 n 的字符串 s，其中 s_i（1≤i≤n）表示第 i 个顶点的颜色（r/g/b 之一）。

第二次运行（玩家 B）输出

对于每组测试用例的每个查询，输出一个整数 j（1≤j≤d(v)），表示 Blackslex 要移动到的邻居 u_j 的索引。

样例输入

第一次运行输入

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
rgb
3
bbr
1
2
rb

第二次运行输出（示例说明）

1
3
1

样例解释

图与染色说明

两组测试用例的图结构和顶点染色如下：

1. 第一组测试用例（n=7，m=8）：染色结果为 "rrgbggr"，即顶点 1-7 的颜色分别为 r、r、g、b、g、g、r。
2. 第二组测试用例（n=4，m=4）：染色结果为 "rbbb"，即顶点 1-4 的颜色分别为 r、b、b、b。

第二次运行查询对应说明

1. 第一组测试用例的 2 个查询：
   • 第一个查询：Blackslex 位于顶点 4，邻居顺序为 6（颜色 g）、2（颜色 r）、7（颜色 r）。选择第 1 个邻居（顶点 6），该顶点距离顶点 1 更近（顶点 4 到 1 的距离为 2，顶点 6 到 1 的距离为 1）。
   • 第二个查询：Blackslex 位于顶点 6，邻居顺序为 5（颜色 g）、4（颜色 b）、1（颜色 r）。选择第 3 个邻居（顶点 1），直接到达目标顶点。
2. 第二组测试用例的 1 个查询：
   • Blackslex 位于顶点 2，邻居顺序为 1（颜色 r）、4（颜色 b）。选择第 1 个邻居（顶点 1），直接到达目标顶点。

注意：

• 样例中第二次运行的输入仅为示例，实际输入会根据第一次运行的染色结果和查询顶点的邻居顺序生成。
• 输出的核心要求是：无论邻居顺序如何，选择的索引对应的邻居必须使 Blackslex 离顶点 1 更近。

提示

• 二分图的关键性质：顶点可按距离顶点 1 的奇偶性分为两层（距离为偶数的顶点集和距离为奇数的顶点集），同一层内无边相连。
• 染色策略需利用二分图分层特性，确保每个非目标顶点 v 的邻居中，“距离更近”的顶点颜色唯一（或具有明确的区分规则），使 Blackslex 能通过邻居颜色直接选择。
• 无需考虑图的具体结构，只需通过染色规则和颜色判断实现“向更近顶点移动”的目标。