## DMOPC '21 Contest 1 P3 - Mystery DAG

View as PDF

Points: 12
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

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?

#### Interaction

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:

Line 1: ?, 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 fflush(stdout) or cout << flush (depending on whether you use printf or cout). In Java, this can be done with System.out.flush(). In Python, you can use sys.stdout.flush().

#### Sample Interaction

>>> 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

#### Sample Explanation

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.