Pink Floyd
Contest: Codeforces Round 549 (Div. 1)
Difficulty rating: 3200
Tags: graphs, interactive

This is an interactive task.

Scientists are about to invent a new optimization for the Floyd-Warshall algorithm, which will allow it to work in linear time. There is only one part of the optimization still unfinished.

It is well known that the Floyd-Warshall algorithm takes a graph with $$$n$$$ nodes and exactly one edge between each pair of nodes. The scientists have this graph, what is more, they have directed each edge in one of the two possible directions.

To optimize the algorithm, exactly $$$m$$$ edges are colored in pink color and all the rest are colored in green. You know the direction of all $$$m$$$ pink edges, but the direction of green edges is unknown to you. In one query you can ask the scientists about the direction of exactly one green edge, however, you can perform at most $$$2 \cdot n$$$ such queries.

Your task is to find the node from which every other node can be reached by a path consisting of edges of same color. Be aware that the scientists may have lied that they had fixed the direction of all edges beforehand, so their answers may depend on your queries.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 100\,000$$$, $$$0 \le m \le 100\,000$$$) — the number of nodes and the number of pink edges.

The next $$$m$$$ lines describe the pink edges, the $$$i$$$-th of these lines contains two integers $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$) — the start and the end of the $$$i$$$-th pink edge. It is guaranteed, that all unordered pairs $$$(u_i, v_i)$$$ are distinct.

Output format:
When you found the answer, print "!" and the number of the node from which every other node can be reached by a single-colored path.

Interaction format:
To ask the direction of the green edge between nodes $$$a$$$ and $$$b$$$, print "?", $$$a$$$ and $$$b$$$ in single line, separated by the space characters.

In answer to this read a single integer, which will be $$$1$$$ if the edge is directed from $$$a$$$ to $$$b$$$ and $$$0$$$ if the edge is directed from $$$b$$$ to $$$a$$$.

You can ask at most $$$2 \cdot n$$$ queries, otherwise you will get Wrong Answer.

After printing a query do not forget to output end of line and flush the output. Otherwise you will get Idleness limit exceeded. To do this, use:

- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see documentation for other languages.

Answer $$$-1$$$ instead of $$$0$$$ or $$$1$$$ means that you made an invalid query or exceeded the query limit. Exit immediately after receiving $$$-1$$$ and you will see Wrong answer verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream.

Hacks

Hacks should be formatted as follows.

The first line should contain two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 300$$$, $$$0 \le m \le n \cdot (n - 1) / 2$$$) — the number of nodes and number of pink edges.

The next $$$m$$$ lines should describe the pink edges, the $$$i$$$-th line should contain 2 integers $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$), which means that there is a pink edge from $$$a_i$$$ to $$$b_i$$$. All unordered pairs $$$(a_i, b_i)$$$ should be distinct.

The next $$$(n \cdot (n - 1) / 2 - m)$$$ lines should describe the green edges, the $$$i$$$-th line should contain two integers $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$)), which means that there is a green edge from $$$a_i$$$ to $$$b_i$$$. All unordered pairs of $$$(a_i, b_i)$$$ should be distinct and should also be different from the pairs for the pink edges.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
In the example above the answer for the query "? 1 3" is 0, so the edge is directed from 3 to 1. The answer for the query "? 4 2" is 1, so the edge is directed from 4 to 2. The answer for the query "? 3 2" is 1, so the edge is directed from 3 to 2. So there are green paths from node 3 to nodes 1 and 2 and there is a pink path from node 3 to node 4.

Example input:
4 2
1 2
3 4
0
1
1

Example output:
? 1 3
? 4 2
? 3 2
! 3

Editorial:
First let's assume that graph has only the green edges and we still don't know their directions. Then we can do the following. We will keep some node which we will call the "top node" and the list of the nodes, that can be reached from the top node. Let's take some node $$$A$$$ which is not reachable and ask about the direction of edge between the top node and $$$A$$$. If the edge goes from top node to $$$A$$$, then we can add $$$A$$$ to the list of reachable nodes and the size of the list will increase by one. If the edge goes from $$$A$$$ to the top node, then we can call $$$A$$$ the new top node, and as the old top node was reachable from $$$A$$$, the list of reachable nodes will remain the same, but the node $$$A$$$ is reachable from itself, so it also will be added to the list. This way after each query we will increase the number of reachable nodes and in $$$n - 1$$$ query we will get the answer.
In our graph we have edges that are coloured in pink, so if we will repeat the described above algorithm, we may get that the edge between top node and $$$A$$$ is coloured in pink. To avoid it, let's create the condensation of pink graph (condensation means the graph of the strongly connected components (later SCC)). As it is a condensation, there always should be some SCCs, that have no incoming edges. Let's call them free SCCs. We will pick some free SCC and pick some node from it and make it top node. Now we will repeat the following: if there are no other free SCC except the one, that contains the top node, all others are reachable from the only free SCC, which means that we have solved the problem. If there is any other top SCC, let's pick some node $$$A$$$ from it. Because this SCC has no incoming edges, the edge between $$$A$$$ and top node is green. So we can repeat the algorithm described above. After that as the node $$$A$$$ is reachable by green color, we can assume that this node is deleted. If it was the last node in it's SCC, we delete this SCC as well and delete all outcoming edges from it. Now some more SCCs may become free. And then we repeat our algorithm. After at most $$$n-1$$$ steps all nodes will be reachable from top one by single coloured path, which means that we have solved the problem.
In out algorithm we need first to create condensation of the graph, which can be done in $$$O(n + m)$$$ time, then we need to remember how many nodes are in each SCC and keep a set of all free SCCs. That can also be done in $$$O(n + m)$$$ time.