You had a directed graph with nodes and edges, but forgot the orientation of each edge. That is, the -th edge could either go from to or from to . Siesta still remembers the orientations, but she insists on keeping it a mystery and not telling you. Instead, she invites you to play the following detective game:
In one question to Siesta, you may ask about two sets of nodes and . In response, she will give you a list of all the edges that go from some node in set to some node in set . To challenge you further, she provides the extra constraint that the sum of the sizes of and over all questions must not exceed .
Your task is to change the orientation of some subset of the edges in the graph such that the resulting graph is acyclic. Can you solve this problem?
This is an interactive problem. The first line contains space-separated integers and .
The next lines each contain space-separated integers and , representing that the -th edge either goes from to or from to . Each edge connects distinct nodes, and there is at most one edge between any nodes.
You will then begin interaction with Siesta. To ask her a question, you should print lines to the output:
?, followed by a space, followed by space-separated integers and .
Line 2: space-separated integers , representing the nodes in set .
Line 3: space-separated integers , representing the nodes in set .
Furthermore, must hold, all must be distinct, and all must be distinct.
In response, you should read in one line from Siesta. This line will contain , followed by space-separated integers , representing the list of the indices of the edges in the graph that go from some node in set to some node in set .
If you believe you have a solution to the problem, you may output
!, followed by a space, followed by a binary string of length . The -th character of this string should be
1 if the -th edge should have its orientation changed, or
0 otherwise. You must terminate your program immediately after performing this operation.
If at any point your output is ill-formatted, you attempt an invalid question, or the sum of exceeds , Siesta will respond with
-1. At this point your program should exit in order to receive a
Wrong Answer verdict.
Please note that you may need to flush
stdout after each operation, or interaction may halt. In C++, this can be done with
cout << flush (depending on whether you use
cout). In Java, this can be done with
System.out.flush(). In Python, you can use
>>> denotes your output. Do not print this out.
4 5 4 1 4 2 2 1 2 3 4 3 >>> ? 2 1 >>> 1 3 >>> 4 2 1 5 >>> ? 1 1 >>> 3 >>> 2 0 >>> ? 4 4 >>> 1 3 2 4 >>> 2 3 4 1 5 3 4 1 5 2 >>> ! 00101
The initial graph is as follows (note that you cannot directly infer the orientations of the edges from the initial input):
After changing the orientation of the -rd and -th edge, as specified in the last line of the sample interaction, the graph looks like this:
This interaction would receive an
Accepted verdict, since the graph is indeed acyclic after changing the specified orientations, and the sum of over all questions does not exceed . Note that only changing the orientation of the -nd edge here would be an equally valid solution.