Pink Floyd

题意翻译

给定一张 $n$ 个点的竞赛图。边分为粉色和绿色。粉色的边有 $m$ 条，你已经知道了它们的方向。而绿色的边你不知道方向。 每次询问，你可以获得一条绿色的边的方向。 你需要在 $2n$ 次询问内，找到一个点 $u$，使得对于每个点 $v$，都有一条 $u\to v$ 的路径，使得路径上每条边同色。需要注意的是路径只能通过粉边和你已经询问的绿边。 交互库是自适应的。 $n, m \leq 10^5$。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

4 2
1 2
3 4
0
1
1

输出样例 #1

? 1 3
? 4 2
? 3 2
! 3

说明

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.

题意翻译

给定一张 $n$ 个点的竞赛图。边分为粉色和绿色。粉色的边有 $m$ 条，你已经知道了它们的方向。而绿色的边你不知道方向。 每次询问，你可以获得一条绿色的边的方向。 你需要在 $2n$ 次询问内，找到一个点 $u$，使得对于每个点 $v$，都有一条 $u\to v$ 的路径，使得路径上每条边同色。需要注意的是路径只能通过粉边和你已经询问的绿边。 交互库是自适应的。 $n, m \leq 10^5$。