这是一个交互问题
金妮正在参加博弈论考试。教授厌倦了一遍又一遍地听到相同的答案,因此他让金妮玩一个游戏,而不是参加标准考试。
从课程中可知,多起始位置图上的组合游戏是有向图和多个起始顶点各持有一个令牌的游戏。两名玩家轮流在每一轮中沿着图的边缘移动一个标记。无法采取行动的玩家输掉游戏。如果双方都能进行无限长的游戏而不输,则称为平局。
在考试中,教授画了一个无环有向图并选择了它的一个顶点。金妮需要猜测教授选择的顶点。为此,Ginny 可以多次选择一组顶点 $$$S$$$ 并询问教授:“如果我在给定图的每个顶点中为多重集 $$$S$$$ 中每次出现的顶点放置一个标记,然后在选定的顶点中再放置一个标记,组合游戏的结果会是什么?”。
分配完任务后,教授离开房间,给金妮一些时间准备比赛。金妮认为她被欺骗了,因为问题无法解决。因此,当教授不在时,她想在图中添加或删除几条边。即使原始图是非循环的,也可以将边添加到图中以使循环出现。
互动
在此任务中,交互由几个阶段组成。
在第一阶段,交互器将三个整数作为程序的输入 $$$N$$$ ($$$1 \le N \le 1000$$$)、$$$M$$$ ($$$0 \le M \le 100\,000$$$)、$$$T$$$ ($$$1 \le T \le 2000$$$):初始图中的顶点和边,以及 Ginny 必须猜测所选顶点的次数。接下来的 $$$M$$$ 行包含顶点对 $$$a_i$$$ $$$b_i$$$ ($$$1 \le a_i, b_i \le N$$$):相应图边的开始和结束。该图保证是非循环的,并且其所有边都是不同的。
解决方案应该打印一个整数 $$$K$$$ ($$$0 \le K \le 4242$$$):图中要更改的边数。接下来的 $$$K$$$ 行应包含“+ $$$a_i$$$ $$$b_i$$$”或“- $$$a_i$$$ $$$b_i$$$”:Ginny 必须相应添加或删除的边的开头和结尾。您可以将预先存在的边添加到图中。操作按照出现的顺序执行,因此允许 Ginny 删除解添加的边。您只能删除现有的边。这些操作可以在图中创建循环。
接下来的 $$$T$$$ 阶段专门用于猜测所选顶点。在每个阶段,解决方案最多可以进行 20 个查询,然后打印答案。要查询多重集 $$$S$$$,解决方案应打印“? $$$|S|~S_1~S_2~\dots~S_{|S|}$$$”。单相中所有多重集的总大小不应超过 20。交互者将回复以下单词之一:
- “获胜”,如果具有多重集 $$$S$$$ 中的代币且所选顶点的组合游戏的获胜者是第一个玩家。
- “输”,如果组合游戏的获胜者是多重集 $$$S$$$ 中的令牌且所选顶点是第二个玩家。
- “平局”,如果带有多重集 $$$S$$$ 中的令牌且选定顶点的组合游戏以平局结束。
- “慢”,如果解决方案发出了第 21 个请求,或者单个阶段中所有多重集的总大小超过 20。在这种情况下,解决方案应终止并收到“错误答案”判决。
一旦猜测到所选顶点,该解决方案就应该打印“! v”。如果所选择的顶点被正确猜测,交互器将打印 Correct,并且解决方案应该继续到猜测的下一阶段,或者如果是最后阶段则完成其执行。否则,交互器将打印“错误”,这意味着解决方案应终止并收到“错误答案”判决。
交互者可以根据图的变化和解决方案操作来更改所选的顶点,但在每个给定的时刻,至少有一个与所有给定的交互者答案相对应的顶点将存在。
黑客格式
黑客攻击具有以下额外限制:
- $$$T = 1$$$
- 您需要指定由交互器选择的单个顶点。
黑客测试格式。输入的第一行包含三个整数$$$N~M~1$$$。输入中接下来的 $$$M$$$ 行包含与输入格式相同的边描述。下一行包含一个整数 $$$v$$$:所选顶点的编号。即使解决方案正确猜测了顶点,黑客也会成功,但该顶点不会是匹配所有执行的查询的唯一顶点。
示例
输入 #1
3 2 3 1 2 2 3 Lose Correct Win Correct Draw Correct
输出 #1
6 + 2 2 - 1 2 + 2 3 - 2 2 + 3 1 + 2 2 ? 0 ! 1 ? 1 2 ! 3 ? 5 1 3 1 3 1 ! 2
注意
在示例测试中,空行表示等待交互另一方的输入。真正的交互器不会打印空行,解决方案也不应该打印它们。
上图展示了示例测试。添加的边缘用红色表示,删除的边缘用虚线绘制。三个猜测阶段表示获得答案的不同方式。
- 如果解决方案仅查询所选顶点,则交互器将返回该顶点的游戏结果。仅当所选顶点的编号为 $$$1$$$ 时,第一个玩家才会失败。
- 如果我们将单个顶点 $$$2$$$ 添加到所选顶点,那么如果所选顶点是 $$$1$$$ 或 $$$2$$$,则游戏应以平局结束。如果选择顶点号 $$$3$$$,则第一个玩家获胜。
- 如果我们在顶点 $$$1$$$ 中放置三个令牌,在顶点 $$$3$$$ 中放置两个令牌,那么仅当选择顶点 $$$2$$$ 时,游戏才会以平局结束。如果教授选择了顶点$$$3$$$,则第一个玩家将获胜,如果教授选择了顶点$$$1$$$,则第二个玩家将获胜。
在第一个测试中,交互器的行为就像所选顶点与上面示例中的顶点相同。但是,如果您在将选项限制为一个顶点之前尝试猜测答案,则即使您打印相同的答案,解决方案也会得到“错误答案”。这是因为如果所选顶点与之前的查询答案一致,则允许交互器更改所选顶点。