markdown E. 粉红弗洛伊德 每个测试点时间限制：$4$ 秒
每个测试点内存限制：$256$ 兆字节
输入：标准输入
输出：标准输出

本题为交互题。

科学家们即将为 Floyd-Warshall 算法发明一种新的优化方法，使其能够在线性时间内运行。目前，该优化方法只剩下最后一部分尚未完成。

众所周知，Floyd-Warshall 算法处理的图有 $n$ 个节点，且每对节点之间恰好有一条边。科学家们拥有这样一张图，并且他们还为每条边指定了两个可能方向中的一个。

为了优化算法，恰好有 $m$ 条边被涂成了粉红色，其余所有边被涂成了绿色。你知道所有 $m$ 条粉红色边的方向，但绿色边的方向是未知的。每次查询，你可以询问科学家们某一条绿色边的方向，但最多只能进行 $2 \cdot n$ 次查询。

你的任务是找到一个节点，使得从该节点出发，沿着同一种颜色的路径可以到达所有其他节点。注意，科学家们可能事先并未固定所有边的方向（即他们可能在说谎），因此他们的回答可能依赖于你的查询。

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

输出
当你找到答案时，输出 ! 和该节点的编号，从该节点出发沿着同色路径可以到达所有其他节点。

交互
要询问节点 $a$ 和 $b$ 之间绿色边的方向，请在一行中输出 ?、$a$ 和 $b$，用空格分隔。
作为回答，你会读入一个整数：如果边是从 $a$ 指向 $b$，则为 $1$；如果边是从 $b$ 指向 $a$，则为 $0$。
你最多可以询问 $2 \cdot n$ 次，否则会得到“答案错误”（Wrong Answer）。
每次输出查询后，不要忘记输出换行并刷新输出缓冲区，否则会得到“超时”（Idleness limit exceeded）。具体方法如下：

• 在 C++ 中：fflush(stdout) 或 cout.flush()
• 在 Java 中：System.out.flush()
• 在 Pascal 中：flush(output)
• 在 Python 中：stdout.flush()
• 其他语言请参考相应文档。

如果回答是 $-1$ 而不是 $0$ 或 $1$，表示你进行了无效查询或超过了查询限制。收到 $-1$ 后应立即退出，否则你可能会看到“答案错误”的判定。否则，由于你的程序会继续从已关闭的流中读取数据，可能会得到任意判定结果。

Hack 数据格式
Hack 数据应按如下格式给出。
第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 300$，$0 \le m \le n \cdot (n-1)/2$）—— 节点数和粉红色边数。
接下来的 $m$ 行描述粉红色边，第 $i$ 行包含两个整数 $a_i$，$b_i$（$1 \le a_i, b_i \le n$，$a_i \ne b_i$），表示有一条从 $a_i$ 到 $b_i$ 的粉红色边。所有无序对 $(a_i, b_i)$ 应互不相同。
接下来的 $n \cdot (n-1)/2 - m$ 行描述绿色边，第 $i$ 行包含两个整数 $a_i$，$b_i$（$1 \le a_i, b_i \le n$，$a_i \ne b_i$），表示有一条从 $a_i$ 到 $b_i$ 的绿色边。所有无序对 $(a_i, b_i)$ 应互不相同，且不能与粉红色边的无序对重复。

输入示例

4 2
1 2
3 4
0
1
1

输出示例

? 1 3
? 4 2
? 3 2
! 3

说明
在上面的示例中，查询 ? 1 3 的回答是 $0$，因此边是从 $3$ 指向 $1$。查询 ? 4 2 的回答是 $1$，因此边是从 $4$ 指向 $2$。查询 ? 3 2 的回答是 $1$，因此边是从 $3$ 指向 $2$。因此，存在从节点 $3$ 到节点 $1$ 和 $2$ 的绿色路径，也存在从节点 $3$ 到节点 $4$ 的粉红色路径。