CF2179F.Blackslex and Another RGB Walking

This is a run-twice (communication) problem.

There are two players: Player A (Agent) and Player B (Blackslex). The jury will first interact with player A. After player A ends their interaction, the jury will interact with player B. Note that player A and player B may not directly pass information to each other; both players are only able to send information or receive information from the jury, but they may agree on the strategy they will use to communicate.

The Penguin Republic is a bipartite connected undirected graph $G$ with $n$ vertices and $m$ edges. Blackslex is going to conduct forbidden field research at vertex $1$. Due to travel restrictions, he will be dropped off at an unknown vertex $v$ ($2 \leq v \leq n$). He must get to vertex $1$ while having no information on the graph.

For his journey, he has bribed a penguin agent and agreed to some communication strategy using the following method; the agent will discreetly mark each vertex in one of the three colors: red, green, or blue. From Blackslex's perspective, he will see only the color $c_i$ of each neighbor $u_i$ ($1 \leq i \leq d(v)$$^{\text{∗}}$) of $v$. He must choose some $j$ ($1 \leq j \leq d(v)$) and move to vertex $u_j$ such that he is closer to vertex $1$.

Note that the neighbors are arbitrarily ordered. He sees only the colors of the neighboring vertices, and not the vertex that he is on. Additionally, he does not know the index of the vertex he's on, the neighboring vertices, or any other vertex.

Your task is to implement the strategy for both the agent and Blackslex. For the agent, you must color each vertex in one of the three colors. For Blackslex, you are given $q$ queries. In each query, you are dropped off at an arbitrary and unknown vertex $v$ and given the color of the neighboring vertices. You must determine a vertex to go to such that you are closer to vertex $1$.

$^{\text{∗}}$The number of neighbors of vertex $v$.

这是一个需运行两次（通信）的问题。

有两个参与者：玩家 A（特工）和玩家 B（Blackslex）。裁判将首先与玩家 A 交互；在玩家 A 的交互结束后，裁判再与玩家 B 交互。注意，玩家 A 和玩家 B 无法直接相互传递信息；双方都只能向裁判发送信息或从裁判处接收信息，但他们可以事先约定彼此将采用的通信策略。

企鹅共和国是一张具有 $n$ 个顶点和 $m$ 条边的二分图连通无向图 $G$。Blackslex 将在顶点 $1$ 处开展禁地研究。但由于旅行限制，他将被随机空投至某个未知顶点 $v$（满足 $2 \leq v \leq n$）。他必须在对图结构一无所知的情况下抵达顶点 $1$。

为完成这段旅程，他贿赂了一只企鹅特工，并约定采用如下通信方式：特工将秘密地将每个顶点染成红、绿、蓝三种颜色之一。从 Blackslex 的视角看，他仅能看到其所在顶点 $v$ 的每个邻接顶点 $u_i$（$1 \leq i \leq d(v)$）的颜色 $c_i$（$^{\text{∗}}$）。他必须从中选择某个 $j$（$1 \leq j \leq d(v)$），并移动到邻接顶点 $u_j$，使得自己离顶点 $1$ 更近。

注意，邻接顶点的顺序是任意的。他仅能看到邻接顶点的颜色，而看不到自己当前所在的顶点本身；此外，他既不知道自己所处顶点的编号，也不知道邻接顶点的编号，更不知道图中任何其他顶点的信息。

你的任务是分别为特工和 Blackslex 实现该通信策略。对于特工，你必须将图中每个顶点染成红、绿、蓝三色之一；对于 Blackslex，你将收到 $q$ 个查询。在每个查询中，你被随机空投至某个未知顶点 $v$，并获知其所有邻接顶点的颜色。你需要据此确定一个应前往的邻接顶点，使得移动后离顶点 $1$ 更近。

$^{\text{∗}}$顶点 $v$ 的邻接顶点数量。

Your code will be ran exactly two times on each test. On the first run, you will be Player A (Agent), and on the second Player B (Blackslex).

First Run Input

The first line of the input contains the string first. The purpose of this is so your program recognizes that this is its first run, and it should act as Player A.

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($2 \leq n \leq 10^5$, $n-1 \leq m \leq 10^5$) — the number of vertices and edges respectively.

The following $m$ lines contain information about the edges. The $i$-th ($1 \leq i \leq m$) line has two integers $a_i$ and $b_i$. ($1 \leq a_i, b_i \leq n$, $a_i \neq b_i$) — vertex $a_i$ is connected to vertex $b_i$ by edge $i$.

It is guaranteed that:

• The sum of $n$ and the sum of $m$ does not exceed $10^5$ over all test cases.
• The graph in each test case is bipartite and connected. It has no duplicate edges and no self-loops.

Second Run Input

The first line of the input contains the string second. The purpose of this is so your program recognizes that this is its second run, and it should act as Player B.

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^4$) — the same value of $t$ in the first run. The description of the test cases follows.

The first line of each test case contains one integer $q$ ($1 \leq q \leq 10^5$) — the number of queries in this test case.

The first line of each query contains one integer $d(v)$ ($1 \leq d(v) \leq 10^5$) — the number of neighbors of the vertex $v$ that Blackslex is currently on.

The next line of each query contains a string $c$ of length $d(v)$ — the $i$-th ($1 \leq i \leq d(v)$) character of the string is the color of the neighboring vertex $u_i$. The characters in the string are r, g, or b representing red, green, or blue.

It is guaranteed that:

• The sum of $q$ does not exceed $10^5$ over all queries in all test cases.
• The sum of $d(v)$ does not exceed $2 \cdot 10^5$ over all queries in all test cases.
• $v \neq 1$

The input of the second run is not adaptive. In other words, the input of the second run will not change in different runs.

Hacks

To make hacks, use the following format:

The first line contains one integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The description of the test cases for the first run follows.

The first line of each test case contains two integers $n$ and $m$ ($2 \leq n \leq 10^5$, $n-1 \leq m \leq 10^5$) — the number of vertices and edges respectively.

The following $m$ lines contain information about the edges. The $i$-th ($1 \leq i \leq m$) line has two integers $a_i$ and $b_i$. ($1 \leq a_i, b_i \leq n$, $a_i \neq b_i$) — vertex $a_i$ is connected to vertex $b_i$ by edge $i$.

After that, the description of the test cases for the second run follows.

The first line of each test case contains one integer $q$ ($1 \leq q \leq 10^5$) — the number of queries in this test case.

The first line of each query contains one integer $v$ ($2 \leq v \leq n$) — the vertex the Blackslex is dropped off.

The second line of each query contains $d(v)$ integers $p_1, p_2, \ldots, p_{d(v)}$ ($1 \leq p_i \leq d(v)$, each number in $p$ is distinct) — the ordering of the neighbor is as follows; let $q_1 \lt q_2 \lt \ldots \lt q_{d(v)}$ be the neighbors of $v$, then the input order of the neighbor is $u_i = q_{p_i}$.

It must hold that:

• The sum of $n$ and the sum of $m$ does not exceed $10^5$ over all test cases in the first run.
• The graph in each test case is bipartite and connected. It has no duplicate edges and no self-loops.
• The sum of $q$ does not exceed $10^5$ over all queries in all test cases.
• The sum of $d(v)$ does not exceed $2 \cdot 10^5$ over all test cases in the second run.

你的代码将在每个测试用例上恰好运行两次。第一次运行时，你将作为玩家 A（Agent）；第二次运行时，你将作为玩家 B（Blackslex）。

第一次运行的输入

输入的第一行包含字符串 first。其作用是让你的程序识别出这是它的第一次运行，此时应以玩家 A 的身份行动。

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \leq t \leq 10^4$）。随后是各测试用例的描述。

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

接下来的 $m$ 行描述各条边的信息。第 $i$ 行（$1 \leq i \leq m$）包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$）——表示顶点 $a_i$ 与顶点 $b_i$ 之间存在第 $i$ 条边。

保证满足以下条件：

• 所有测试用例中，$n$ 的总和与 $m$ 的总和均不超过 $10^5$。
• 每个测试用例中的图均为二分图且连通；图中无重边，也无自环。

第二次运行的输入

输入的第一行包含字符串 second。其作用是让你的程序识别出这是它的第二次运行，此时应以玩家 B 的身份行动。

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \leq t \leq 10^4$）——该值与第一次运行中的 $t$ 相同。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $q$（$1 \leq q \leq 10^5$）——表示该测试用例中查询的数量。

每个查询的第一行包含一个整数 $d(v)$（$1 \leq d(v) \leq 10^5$）——表示 Blackslex 当前所处顶点 $v$ 的邻居数量。

每个查询的第二行包含一个长度为 $d(v)$ 的字符串 $c$——其中第 $i$ 个字符（$1 \leq i \leq d(v)$）表示第 $i$ 个邻居顶点 $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$ 行描述各条边的信息。第 $i$ 行（$1 \leq i \leq m$）包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$）——表示顶点 $a_i$ 与顶点 $b_i$ 之间存在第 $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$ 中各数互不相同）——邻居的顺序定义如下：设 $v$ 的邻居按升序排列为 $q_1 < q_2 < \ldots < q_{d(v)}$，则输入中邻居的顺序为 $u_i = q_{p_i}$。

必须满足以下条件：

• 第一次运行的所有测试用例中，$n$ 的总和与 $m$ 的总和均不超过 $10^5$。
• 每个测试用例中的图均为二分图且连通；图中无重边，也无自环。
• 所有测试用例中所有查询的 $q$ 总和不超过 $10^5$。
• 第二次运行的所有测试用例中，所有 $d(v)$ 的总和不超过 $2 \cdot 10^5$。

For the first run, for each test case, output a single string $s$ of length $n$ — $s_i$ ($1 \leq i \leq n$) is the color of the $i$-th vertex, painted by the agent. The characters in the string are r, g, or b representing red, green, or blue.

For the second run, for each query in each test case, output a single integer $j$ ($1 \leq j \leq d(v)$) — $u_j$ is the neighboring vertex that Blackslex will go to next.

首次运行时，对每个测试用例，输出一个长度为 $n$ 的字符串 $s$ — 其中 $s_i$（$1 \leq i \leq n$）表示智能体为第 $i$ 个顶点所涂的颜色。字符串中的字符为 r、g 或 b，分别代表红色、绿色或蓝色。

第二次运行时，对每个测试用例中的每个查询，输出一个整数 $j$（$1 \leq j \leq d(v)$）— 其中 $u_j$ 是 Blackslex 下一步将前往的邻接顶点。

Graph and coloring of both tests.

In the sample, there are two test cases. The graph and the sample's vertex coloring are demonstrated in the picture above.

In the second run, the first test case has two queries.

The first query is on vertex $4$ with the neighbors ordered as vertex $6$, $2$, and $7$. Choosing the first neighbor is walking to vertex $6$.

The second query is on vertex $6$ with the neighbors ordered as vertex $5$, $4$, and $1$. Choosing the third neighbor is walking to vertex $1$.

The second test case has a single query on vertex $2$ with the neighbors ordered as vertex $1$ and $4$. Choosing the first neighbor is walking to vertex $1$.

Note that the empty lines are made to assist reading. Actual test cases do not have empty lines.

[In-contest only] Link to image in case of the image not loading: https://ibb.co/yFZS16vj

两个测试用例的图及其顶点着色。

样例中包含两个测试用例。上图展示了该样例中的图及其顶点着色方案。

在第二次运行中，第一个测试用例包含两个查询。

第一个查询针对顶点 $4$，其邻接点按顶点 $6$、$2$、$7$ 的顺序排列。选择第一个邻接点即走向顶点 $6$。

第二个查询针对顶点 $6$，其邻接点按顶点 $5$、$4$、$1$ 的顺序排列。选择第三个邻接点即走向顶点 $1$。

第二个测试用例仅含一个查询，针对顶点 $2$，其邻接点按顶点 $1$、$4$ 的顺序排列。选择第一个邻接点即走向顶点 $1$。

注意：空行仅为便于阅读而设置，实际测试用例中不包含空行。

[仅限比赛期间使用] 若图片无法加载，请通过以下链接查看：https://ibb.co/yFZS16vj