CF1142E.Pink Floyd

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.

这是一个交互式题目。

科学家们即将发明一种 Floyd-Warshall 算法的新优化方法，使其能在线性时间内运行。但该优化中尚有一部分尚未完成。

众所周知，Floyd-Warshall 算法接收一个包含 $n$ 个节点的图，并且每对节点之间恰好存在一条边。科学家们拥有这样的图，而且他们已将每条边定向为两个可能方向中的一个。

为了实现该优化，恰好 $m$ 条边被染成粉色，其余所有边均被染成绿色。你已知全部 $m$ 条粉色边的方向，但所有绿色边的方向对你而言是未知的。每次查询，你可以向科学家询问某一条特定绿色边的方向；然而，你最多只能进行 $2 \cdot n$ 次此类查询。

你的任务是：找出一个节点，使得从该节点出发，能够仅通过同一种颜色（即全为粉色或全为绿色）的边构成的路径到达图中其余每一个节点。

请注意：科学家们可能并未如其所声称的那样在事先就固定了所有边的方向，因此他们的回答可能依赖于你所提出的查询。

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.

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 100\,000$，$0 \le m \le 100\,000$）—— 分别表示节点数和粉色边的数量。

接下来的 $m$ 行描述粉色边，其中第 $i$ 行包含两个整数 $u_i$、$v_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$）—— 表示第 $i$ 条粉色边的起点和终点。保证所有无序对 $(u_i, v_i)$ 互不相同。

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.

当你找到答案时，输出“!”以及从该节点出发，可通过单色路径到达所有其他节点的节点编号。

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.

在上面的例子中，查询 “? 1 3” 的答案为 0，因此该边的方向为从 3 指向 1；查询 “? 4 2” 的答案为 1，因此该边的方向为从 4 指向 2；查询 “? 3 2” 的答案为 1，因此该边的方向为从 3 指向 2。因此，存在从节点 3 到节点 1 和节点 2 的绿色路径，以及一条从节点 3 到节点 4 的粉色路径。