#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
#define int long long
const int maxn = 5e4 + 69;
vector<int> g[maxn];
int n, m, deg[maxn], par[maxn], cnt[maxn];
signed main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   int tt = 1;
   //cin >> tt;
   while(tt--) {
		cin >> n >> m;
		set<pair<int, int>> edges;
		for (int i = 1;i <= m;i++) {
			int x, y;
			cin >> x >> y;
			if (x > y)
				swap(x, y);
			edges.insert({x, y});
		}
		int ans = 0;
		while (1) {
			for (int i = 1;i <= n;i++) {
				g[i].clear();
				deg[i] = cnt[i] = par[i] = 0;
			}
			for (auto x : edges) {
				int a, b;
				tie(a, b) = x;
				g[a].push_back(b);
				deg[b]++;
			}
			queue<int> q;
			for (int i = 1;i <= n;i++) {
				if (deg[i] == 0)
					q.push(i);
			}
			while (!q.empty()) {
				auto v = q.front();
				q.pop();
				for (auto u : g[v]) {
					deg[u]--;
					if (cnt[v] + 1 >= cnt[u])
						par[u] = v;
					cnt[u] = max(cnt[u], cnt[v] + 1);
					if (deg[u] == 0)
						q.push(u);
				}
			}
			vector<int> v;
			int mx = 0, t;
			for (int i = 1;i <= n;i++) {
				if (cnt[i] >= mx) {
					t = i;
					mx = cnt[i];
				}
			}
			while (t != 0) {
				v.push_back(t);
				t = par[t];
			}
			reverse(v.begin(), v.end());
			int ok = 0;
			for (int i = 1;i < (int)v.size();i++) {
				int a = v[i - 1], b = v[i];
				if (a > b)
					swap(a, b);
				cout << "? " << v[i - 1] << " " << v[i] << endl;
				int r;
				cin >> r;
				if (r == 0) {
					ans = max(ans, cnt[a]);
					edges.erase({a, b});
					ok = 1;
					break;
				}
			}
			if (!ok) 	
				break;

		}
		cout << "! " << ans << endl;
   }
   return 0;
}