这是一个交互式问题。在打印每一行后，你必须使用 flush 操作。例如，在 C 或 C++ 中可以使用 fflush(stdout)，在 Java 中可以使用 System.out.flush()，在 Pascal 中可以使用 flush(output)，在 Python 中可以使用 sys.stdout.flush()。

你是一名数据分析部门的普通员工。然而，你的同事似乎是制造麻烦的天才。刚才他们又惹麻烦了。

他们从远程服务器下载了一个大型图，并编写了一个程序来分析该图。他们快要完成分析时，认为该图不再有用了，于是让程序在没有备份的情况下向图中添加了一些新边。但随后他们改变了主意，想要计算原始图中的最长路径。重新下载该图太耗时了。现在轮到你来拯救局面了。

远程服务器上的原始图是一个有向无环图 $G = (V, E)$。所有边的长度均为单位长度。你程序的输入是修改后的版本 $G' = (V, E')$。保证 $E \subseteq E'$，且 $G'$ 是一个有向无环图。

你的程序应该输出 $\ell(G)$，即图 $G$ 中最长路径的长度。路径的长度等于路径中边的数量。

为了测试一条边是否属于原始图，你的程序可以向远程服务器发起查询。要查询边 $u \to v$ 是否存在，输出 ? u v。在打印每个查询后，请刷新输出流。如果边 $u \to v$ 属于原始图，远程服务器将返回 1，否则返回 0。

在你的程序得到答案后，打印 ! ans，其中 $ans = \ell(G)$，并在刷新输出流后立即正常终止程序。

你的程序最多被允许向远程服务器发起 $(|E'| - |E| + 1) \cdot (\ell(G) + 1)$ 次查询（不包括打印答案的步骤），尽管你并不知道 $|E|$ 和 $\ell(G)$ 的值。

输入格式

使用标准输入读取对查询的响应。

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 5 \cdot 10^4; 1 \le m \le 10^5$)：图 $G'$ 的顶点数和边数。

接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n$)，指定了图 $G'$ 中的一条有向边 $u \to v$。没有边会出现超过一次。

保证 $0 \le |E'| - |E| \le 200$。

接下来的行将包含对你查询的响应。每个响应要么是 “0”，要么是 “1”。这些行中的第 $i$ 行是对你第 $i$ 次查询的响应。

在回答了 $(|E'| - |E| + 1) \cdot (\ell(G) + 1)$ 次查询后，远程服务器将不再响应。

测试系统只允许你在程序打印查询并执行 flush 操作后读取查询的响应。

输出格式

为了进行查询，你的程序必须使用标准输出。

你的程序必须以 ? u v 的形式打印查询，每行一个查询。不要忘记在每个查询后换行。你的程序必须保证 $1 \le u, v \le n$。在打印每一行后，你的程序必须执行 flush 操作。

查询的响应将会在你刷新输出后通过标准输入给出。当你的程序找到答案时，打印一行 ! ans，其中 $ans = \ell(G)$，并终止你的程序。

样例

样例输入 1

5 5
1 2
1 3
2 5
3 4
4 5
1
1
1
0
1

样例输出 1

? 1 2
? 1 3
? 2 5
? 3 4
? 4 5
! 2