CF1442F.Differentiating Games

This is an interactive problem

Ginny is taking an exam on game theory. The professor is tired of hearing the same answers over and over again, so he offered Ginny to play a game instead of a standard exam.

As known from the course, a combinatorial game on a graph with multiple starting positions is a game with a directed graph and multiple starting vertices holding a token each. Two players take turns moving one of the tokens along the graph edges on each turn. The player who can't make a move loses the game. If both players can play an infinitely long game without losing, a draw is called.

For the exam, the professor drew an acyclic directed graph and chose one of its vertices. Ginny needs to guess the vertex the professor chose. To do so, Ginny can choose a multiset of vertices $S$ several times and ask the professor: "If I put one token in each vertex of the given graph for each occurrence of the vertex in the multiset $S$, and then one more in the selected vertex, what would be the result of the combinatorial game?".

Having given the task, the professor left the room to give Ginny some time to prepare for the game. Ginny thinks that she's being tricked because the problem is impossible to solve. Therefore, while the professor is away, she wants to add or remove several edges from the graph. Even though the original graph was acyclic, edges could be added to the graph to make cycles appear.

Interaction

In this task, interaction consists of several phases.

In the first phase, the interactor gives as an input to your program three integers $N$ ($1 \le N \le 1000$), $M$ ($0 \le M \le 100\,000$), $T$ ($1 \le T \le 2000$): the number of vertices and edges in the initial graph, and the number of times Ginny has to guess the chosen vertex. The next $M$ lines contain pairs of vertices $a_i$ $b_i$ ($1 \le a_i, b_i \le N$): beginning and end of corresponding graph edges. The graph is guaranteed to be acyclic and all of its edges to be distinct.

The solution should print an integer $K$ ($0 \le K \le 4242$): the number of edges to change in the graph. The next $K$ lines should contain either "+ $a_i$ $b_i$" or "- $a_i$ $b_i$": the beginning and the end of an edge that Ginny has to add or remove accordingly. You are allowed to add preexisting edges to the graph. Operations are performed in the order of appearance, so Ginny is allowed to remove an edge added by the solution. You can only remove an existing edge. The operations can create cycles in the graph.

The next $T$ phases are dedicated to guessing the chosen vertices. In each phase, the solution can make at most 20 queries and then print the answer. To query a multiset $S$, the solution should print "? $|S|~S_1~S_2~\dots~S_{|S|}$". The total size of all multisets in a single phase should not exceed 20. The interactor will reply with one of the following words:

• "Win", if the winner of a combinatorial game with tokens in multiset $S$ and the selected vertex is the first player.
• "Lose", if the winner of a combinatorial game with tokens in multiset $S$ and the selected vertex is the second player.
• "Draw", if a combinatorial game with tokens in multiset $S$ and selected vertex ends in a draw.
• "Slow", if the solution made a 21-st request, or the total size of all multisets in a single phase exceeded 20. In this case, the solution should terminate and receive Wrong Answer verdict.

As soon as the selected vertex is guessed, that solution should print "! v". If the chosen vertex is guessed correctly, the interactor will print Correct and the solution should either move on to the next phase of guessing or finish its execution if it's the last phase. Otherwise, the interactor will print Wrong, which means that the solution should terminate and will receive the Wrong Answer verdict.

The interactor can change the chosen vertex based on graph changes and solution actions, but at every given moment of time, at least one vertex that corresponds to all given interactor answers will exist.

Hack format

Hacks have the following extra limitations:

• $T = 1$
• you need to specify a single vertex, chosen by the interactor.

Hack test format. The first line of input contains three integers $N~M~1$. The next $M$ lines on input contain edge description in the same format as in the input. The next line contains a single integer $v$: the number of the chosen vertex. The hack will be successful even if the solution guesses the vertex right, but the vertex will not be the single one to match all performed queries.

这是一个交互式问题。

金妮正在参加一场博弈论考试。教授厌倦了反复听到相同的答案，因此他给金妮提供了一个游戏，代替标准的笔试考试。

根据课程所学，图上的组合博弈（含多个起始位置） 是指：给定一个有向图，以及若干个起始顶点，每个起始顶点上放置一枚棋子。两名玩家轮流操作，每次选择一枚棋子，沿图中的一条有向边将其移动到相邻顶点。无法进行合法移动的玩家判负。若双方均可无限进行游戏而永不失败，则称该局为平局（Draw）。

为本次考试，教授画出了一张有向无环图（DAG），并从中选定一个顶点。金妮需要猜出教授选定的是哪一个顶点。为此，她可多次选择一个顶点多重集 $S$，并向教授提问：“如果我在图中对 $S$ 中每个顶点的每次出现都放置一枚棋子，并额外在教授选定的顶点上再放一枚棋子，那么该组合博弈的结果是什么？”

布置完任务后，教授离开了教室，让金妮有时间准备这场游戏。金妮认为自己被耍了，因为这个问题根本无法解决。因此，在教授离开期间，她打算对图进行若干次添加或删除边的操作。尽管原图是无环的，但允许添加边以引入环。

---

交互流程

本题的交互分为若干阶段。

第一阶段（图修改阶段）

评测器首先向你的程序输入三个整数：
$N$（$1 \le N \le 1000$）——图的顶点数，
$M$（$0 \le M \le 100\,000$）——初始图的边数，
$T$（$1 \le T \le 2000$）——金妮需猜出选定顶点的次数。

接下来 $M$ 行，每行包含两个整数 $a_i$、$b_i$（$1 \le a_i, b_i \le N$），表示一条从 $a_i$ 指向 $b_i$ 的有向边。
保证初始图为有向无环图（DAG），且所有边互不相同。

你的程序应输出一个整数 $K$（$0 \le K \le 4242$）：表示需对图执行的边变更操作总数。
随后 $K$ 行，每行格式为：

• \+ $a_i$ $b_i$：表示添加一条从 $a_i$ 到 $b_i$ 的边；或
• \- $a_i$ $b_i$：表示删除一条从 $a_i$ 到 $b_i$ 的边。

你可以添加已存在的边（即允许重复添加）；所有操作按顺序依次执行，因此你可以删除由你先前添加的边；但仅能删除图中原本存在的边（即不能删除你刚添加、尚未存在的边）。这些操作可能导致图中出现环。

后续 $T$ 阶段（顶点猜测阶段）

接下来的 $T$ 个阶段分别对应 $T$ 次独立的顶点猜测任务。在每一阶段中：

• 你的程序最多可发出 20 次查询，之后必须输出答案；
• 每次查询一个多重集 $S$，需输出：? $|S|~S_1~S_2~\dots~S_{|S|}$；
• 单阶段内所有查询的多重集总大小（即所有 $|S|$ 之和）不得超过 20。

评测器将针对每次查询返回以下四个字符串之一：

• "Win"：若在多重集 $S$ 所含棋子位置基础上，再于选定顶点加放一枚棋子后，该组合博弈的先手必胜；
• "Lose"：若上述局面下，后手必胜；
• "Draw"：若上述局面下，博弈结果为平局；
• "Slow"：若你在该阶段发出了第 21 次查询，或该阶段所有多重集的总大小超过 20。此时你的程序应立即终止，并被判为 Wrong Answer。

一旦你猜中当前选定的顶点 $v$，请输出：! v。
若猜测正确，评测器将输出 Correct，此时你的程序应继续进入下一猜测阶段（若非最后一阶段），或直接结束；
若猜测错误，评测器将输出 Wrong，你的程序应立即终止，并被判为 Wrong Answer。

注意：评测器可根据图的修改及你的操作动态调整所选顶点，但在任意时刻，至少存在一个顶点满足此前所有已给出的评测器响应。

---

Hack 格式（特殊测试用例格式）

Hack 用例附加如下限制：

• $T = 1$（仅需猜一次）；
• 你必须明确指定评测器所选定的唯一顶点。

Hack 测试用例格式如下：
第一行输入三个整数：$N~M~1$；
接下来 $M$ 行，按与主输入相同格式给出边；
下一行输入一个整数 $v$：即评测器选定的顶点编号。

即使你的程序恰好猜中了 $v$，但如果该 $v$ 并非唯一满足所有已执行查询响应的顶点，则该 hack 仍视为成功。

In the sample test, the empty lines represent waiting for the input by the other side of the interaction. The real interactor will not print empty lines, and the solution should not print them either.

The image above illustrates the sample test. Added edges are coloured in red, and the removed edges are drawn with a dotted line. Three guessing phases denote different ways of getting the answer.

• If the solution will query just the chosen vertex, the interactor will return the result of the game in that vertex. The first player loses only if the chosen vertex has the number $1$.
• If we add a single vertex $2$ to the chosen vertex, then if the chosen vertex is either $1$ or $2$, the game should end in a draw. If vertex number $3$ is chosen, then the first player wins.
• If we place three tokens in vertex $1$ and two tokens in vertex $3$, then the game will end in a draw only if vertex $2$ is chosen. If the professor chose vertex $3$, the first player will win, if the professor chose vertex $1$, then the second player will win.

In the first test, the interactor will behave as if the chosen vertices are the same as those in the example above. However, if you will try to guess the answer before it limits the options to one single vertex, the solution will get "Wrong Answer", even if you print the same answers. That's because the interactor is allowed to change the chosen vertex if it's consistent with the previous query answers.

在样例测试中，空行表示正在等待交互的另一方输入。真实的交互器不会输出空行，你的程序也不应输出空行。

上图展示了该样例测试。新增的边以红色标出，被删除的边以虚线表示。三个猜测阶段代表了三种不同的获取答案的方式：

• 若你的程序仅向所选顶点发起一次查询，则交互器将返回该顶点处博弈的结果。先手玩家仅当所选顶点编号为 $1$ 时才会失败。
• 若我们在所选顶点上额外添加一个顶点 $2$（即向所选顶点与顶点 $2$ 同时放置棋子），则：若所选顶点为 $1$ 或 $2$，博弈将以平局结束；若所选顶点为 $3$，则先手玩家获胜。
• 若我们在顶点 $1$ 放置三枚棋子、在顶点 $3$ 放置两枚棋子，则：仅当所选顶点为 $2$ 时，博弈才会以平局结束；若教授选定顶点 $3$，则先手玩家获胜；若教授选定顶点 $1$，则后手玩家获胜。

在第一个测试用例中，交互器的行为将与上述示例中选定的顶点完全一致。然而，如果你在尚未将可能的顶点选项缩小至唯一一个时就尝试猜测答案，则你的程序将被判为“答案错误”（Wrong Answer），即使你输出的答案与正确答案相同。这是因为交互器被允许在满足此前所有查询回答的前提下，动态更改其选定的顶点。