Too Many Edges

This is an interactive problem. You have to use the flush operation right after printing each line. For example, you can use fflush(stdout) in C or C++, System.out.flush() in Java, flush(output) in Pascal, and sys.stdout.flush() in Python.

You are an ordinary employee of a data analysis department. Your colleagues made trouble again. They downloaded a large graph from a remote server and analyzed it. Then their program added new edges to the graph without making a backup. Now they want the longest path in the original graph. Downloading the graph again takes too long, so you must recover the answer.

The original graph on the remote server is a directed acyclic graph $G=(V,E)$. All edges have unit length. Your input is a modified graph $G'=(V,E')$, where $E\subseteq E'$ and $G'$ is a directed acyclic graph.

Your program must output $\ell(G)$, the length of the longest path in $G$. The length of a path is the number of edges in it.

To test whether an edge belongs to the original graph, your program can query the remote server. To query whether edge $u \to v$ belongs to $G$, print ? u v. Flush the output after each query. The server responds with 1 if the edge is in $G$ and 0 otherwise.

When you know the answer, print ! ans, where $ans = \ell(G)$. Flush the output and terminate the program normally.

Your program may make at most $(|E'| - |E| + 1) \times (\ell(G) + 1)$ queries (not counting the answer line), although $|E|$ and $\ell(G)$ are unknown to you.

The first line contains two integers $n$ and $m$ ($1 \le n \le 5 \cdot 10^4$; $1 \le m \le 10^5$): the number of vertices and edges of $G'$.

Each of the next $m$ lines contains two integers $u$ and $v$ ($1 \le u, v \le n$) describing a directed edge $u \to v$ in $G'$. No edge appears more than once. It is guaranteed that $0 \le |E'| - |E| \le 200$.

The following lines contain the responses to your queries, each 0 or 1. The $i$-th of these lines responds to your $i$-th query. After $(|E'| - |E| + 1) \times (\ell(G) + 1)$ queries, the server stops responding. The server sends a response only after your program prints a query and flushes the output.

Print each query as ? u v on its own line, with $1 \le u, v \le n$. Flush the output after every line. When you find the answer, print ! ans on its own line and terminate the program.