这是一个运行两次(通信)问题。
有两名玩家:玩家 A(特工)和玩家 B(Blackslex)。陪审团首先会与玩家A进行互动。玩家A结束互动后,陪审团将与玩家B进行互动。注意,玩家A和玩家B不能直接向对方传递信息;双方玩家只能发送信息或从陪审团接收信息,但他们可以就沟通策略达成一致。
企鹅共和国是一个 双方 连接无向图 $$$G$$$ 与 $$$n$$$ 个顶点和 $$$m$$$ 边。 Blackslex 将在顶点 $$$1$$$ 进行禁域研究。由于旅行限制,他将在未知地点 $$$v$$$ ($$$2 \leq v \leq n$$$) 下车。他必须到达顶点 $$$1$$$,同时图上没有任何信息。
在他的旅程中,他贿赂了企鹅代理人并同意使用以下方法的一些沟通策略;代理将谨慎地用三种颜色之一标记每个顶点:红色、绿色或蓝色。从 Blackslex 的角度来看,他只会看到 $$$v$$$ 的每个邻居 $$$u_i$$$ ($$$1 \leq i \leq d(v)$$$$$$^{\text{∗}}$$$) 的颜色 $$$c_i$$$。他必须选择一些 $$$j$$$ ($$$1 \leq j \leq d(v)$$$) 并移动到顶点 $$$u_j$$$,以便他更接近顶点 $$$1$$$。
请注意,邻居是任意排序的。他只能看到相邻顶点的颜色,而看不到他所在的顶点。此外,他不知道他所在的顶点、相邻顶点或任何其他顶点的索引。
您的任务是为代理和 Blackslex 实施策略。对于代理,您必须将每个顶点着色为三种颜色之一。对于 Blackslex,您会收到 $$$q$$$ 查询。在每个查询中,您都会在任意未知的顶点 $$$v$$$ 处下车,并给出相邻顶点的颜色。您必须确定要前往的顶点,以便您更接近顶点 $$$1$$$。
$$$^{\text{*}}$$$顶点$$$v$$$的邻居数量。
输入
您的代码将在每次测试中运行两次。在第一次运行中,您将成为玩家 A(特工),在第二次运行中,您将成为玩家 B(Blackslex)。
首次运行输入
输入的第一行包含字符串 第一。这样做的目的是让您的程序认识到这是它的第一次运行,并且它应该充当玩家 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$$$ 通过边 $$$i$$$ 连接到顶点 $$$b_i$$$。
保证:
- 所有测试用例中 $$$n$$$ 的总和与 $$$m$$$ 的总和不超过 $$$10^5$$$。
- 每个测试用例中的图都是二部且连通的。它没有重复的边,也没有自环。
第二次运行输入
输入的第一行包含字符串 第二。这样做的目的是让您的程序认识到这是它的第二次运行,并且它应该充当玩家 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)$$$) 字符是相邻顶点 $$$u_i$$$ 的颜色。字符串中的字符是 r, g,或 b 代表红色、绿色或蓝色。
保证:
- 所有测试用例中所有查询的 $$$q$$$ 总和不超过 $$$10^5$$$。
- 所有测试用例中所有查询的 $$$d(v)$$$ 总和不超过 $$$2 \cdot 10^5$$$。
- $$$v \neq 1$$$
第二次运行的输入不自适应。换句话说,第二次运行的输入在不同的运行中不会改变。
黑客
要进行 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$$$ 通过边 $$$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 \lt q_2 \lt \ldots \lt q_{d(v)}$$$ 为 $$$v$$$ 的邻居,则邻居的输入顺序为 $$$u_i = q_{p_i}$$$。
必须认为:
- 在第一次运行的所有测试用例中,$$$n$$$ 的总和与 $$$m$$$ 的总和不超过 $$$10^5$$$。
- 每个测试用例中的图都是二部且连通的。它没有重复的边,也没有自环。
- 所有测试用例中所有查询的 $$$q$$$ 总和不超过 $$$10^5$$$。
- 第二次运行中所有测试用例的 $$$d(v)$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于第一次运行,对于每个测试用例,输出长度为 $$$n$$$ 的单个字符串 $$$s$$$ — $$$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