간선이 너무 많음

이 문제는 대화형 문제입니다. 각 줄을 출력한 직후에 flush 연산을 사용해야 합니다. 예를 들어 C나 C++에서는 fflush(stdout), Java에서는 System.out.flush(), Pascal에서는 flush(output), Python에서는 sys.stdout.flush()를 사용할 수 있습니다.

당신은 데이터 분석 부서의 일반 직원입니다. 동료들이 또 문제를 일으켰습니다. 그들은 원격 서버에서 큰 그래프를 내려받아 분석했습니다. 그런 다음 프로그램이 백업 없이 그래프에 새 간선을 추가했습니다. 이제 그들은 원래 그래프의 최장 경로를 알고 싶어 합니다. 그래프를 다시 내려받으면 시간이 너무 오래 걸리므로, 답을 복원해야 합니다.

원격 서버에 있는 원래 그래프는 방향 비순환 그래프 $G=(V,E)$입니다. 모든 간선의 길이는 1입니다. 입력은 수정된 그래프 $G'=(V,E')$이며, $E\subseteq E'$이고 $G'$는 방향 비순환 그래프임이 보장됩니다.

프로그램은 $G$에서의 최장 경로 길이 $\ell(G)$를 출력해야 합니다. 경로의 길이는 경로에 포함된 간선의 수입니다.

어떤 간선이 원래 그래프에 속하는지 확인하기 위해 서버에 질의할 수 있습니다. 간선 $u \to v$가 $G$에 속하는지 물으려면 ? u v를 출력하세요. 질의마다 출력을 플러시하세요. 간선이 $G$에 있으면 서버는 1을, 없으면 0을 응답합니다.

답을 알면 ! ans를 출력하세요. 여기서 $ans = \ell(G)$입니다. 출력을 플러시한 뒤 프로그램을 정상 종료하세요.

질의는 최대 $(|E'| - |E| + 1) \times (\ell(G) + 1)$번까지 할 수 있습니다(답을 출력하는 줄은 제외). 다만 $|E|$와 $\ell(G)$는 알 수 없습니다.

첫 줄에는 두 정수 $n$과 $m$ ($1 \le n \le 5 \cdot 10^4$; $1 \le m \le 10^5$)이 주어집니다. 이는 $G'$의 정점 수와 간선 수입니다.

이어지는 $m$개의 줄에는 각각 $G'$의 방향 간선 $u \to v$를 나타내는 두 정수 $u$, $v$ ($1 \le u, v \le n$)가 주어집니다. 같은 간선이 두 번 나오지 않습니다. $0 \le |E'| - |E| \le 200$이 보장됩니다.

그 다음 줄들에는 질의에 대한 응답이 0 또는 1로 주어집니다. $i$번째 줄은 $i$번째 질의에 대한 응답입니다. $(|E'| - |E| + 1) \times (\ell(G) + 1)$번의 질의 후에는 서버가 더 이상 응답하지 않습니다. 서버는 프로그램이 질의를 출력하고 플러시한 뒤에만 응답합니다.

질의는 ? u v 형식으로, 한 줄에 하나씩 출력하세요. $1 \le u, v \le n$을 만족해야 합니다. 각 줄을 출력한 뒤에는 출력을 플러시하세요. 답을 찾으면 ! ans를 한 줄에 출력하고 프로그램을 종료하세요.