#include "bits/stdc++.h"
using namespace std;

using ll = long long;
using LL = long long;
using pii = pair<int, int>;

int n, m;
vector<int> v[50005];
int in[50005];
int dis[50005];
int out[50005];
vector<int> possible;
vector<int> bk[50005];

unordered_map<LL, bool> M;
bool hv(LL u, LL v) {
	LL tmp = u * (m + 1) + v;
	if (M.find(tmp) == M.end()) {
		M[tmp] = true;
		return false;
	}
	return true;
}
int ask(int u, int v) {
	cout << "? " << u << " " << v << "\n";
	cout.flush();
	int ans;
	cin >> ans;
	return ans;
}
void redo(int x) {
	int before = dis[x];
	dis[x] = 0;
	for (auto i : bk[x]) {
		dis[x] = max(dis[x], dis[i] + 1);
	}
	if (dis[x] == before) return;
	for (auto i : v[x]) redo(i);
}
void solve(int TC) {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int r1, r2;
		cin >> r1 >> r2;
		v[r1].push_back(r2);
		bk[r2].push_back(r1);
		in[r2]++;
		out[r1]++;
	}
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (in[i] == 0) q.push(i);
		dis[i] = 0;
	}
	while (q.size()) {
		auto pr = q.front();
		q.pop();
		for (auto i : v[pr]) {
			dis[i] = max(dis[i], dis[pr] + 1);
			in[i]--;
			if (in[i] == 0) q.push(i);
		}
	}
	for (int i = 1; i <= n; i++) {
		possible.push_back(i);
	}
	while (true) {
		int mx = 0;
		int id;
		for (auto i : possible) {
			if (dis[i] > mx) {
				mx = dis[i];
				id = i;
			}
		}
		bool reach = true;
		while (dis[id] > 0) {
			int pt;
			for (auto i : bk[id]) {
				if (dis[i] == dis[id] - 1) {
					pt = i;
					break;
				}
			}
			if (hv(pt, id)) id = pt;
			else {
				int ans = ask(pt, id);
				if (ans == 1) id = pt;
				else {
					auto iter = find(v[pt].begin(), v[pt].end(), id);
					v[pt].erase(iter);
					auto iter2 = find(bk[id].begin(), bk[id].end(), pt);
					bk[id].erase(iter2);
					redo(id);
					reach = false;
					break;
				}
			}
		}
		if (reach) {
			cout << "! " << mx << "\n";
			cout.flush();
			break;
		}
	}
	return;
}

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	cout << fixed << setprecision(10);

	int t = 1;
	// cin >> t;

	for (int i = 1; i <= t; i++) {
		solve(i);
	}
}