#include <bits/stdc++.h>

/*
	Oce nas,
	koji si na nebesima,
	da se sveti ime Tvoje,
	da dodje carstvo Tvoje,
	da bude volja Tvoja,
	i na zemlji, kao i na nebu.
	
	Hleb nas nasusni daj nam danas,
	i oprosti nam dugove nase,
	kao sto i mi oprastamo duznicima svojim,
	i ne uvedi nas u iskusenje,
	no izbavi nas od zloga.
	
	Jer je Tvoje Carstvo,
	i sila, i slava,
	u vekove vekova.
	
	Amin.
*/

using namespace std;
typedef vector<int> vc;
typedef vector<vector<int>> vvc;
using ll = long long;
using ld = long double;
#define F first
#define S second
#define pb push_back
#define pf push_front
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define int long long

const int N = 5e4+3;
set<int> adj[N];
set<int> revadj[N];
vector<int> toposorted;
bool mark[N];
int d[N];
map<pair<int, int>, int> asked;
int p[N];
int prevans=0;

void dfs(int v){
	mark[v]=1;
	for(auto to =adj[v].begin(); to!=adj[v].end(); to++){
		int nd=*to;
		if(!mark[nd])dfs(nd);
	}
	toposorted.pb(v);
}

void sortbydist(int n){
	for(int i=1; i<=n; i++){
		d[i]=0;
		mark[i]=0;
		p[i]=0;
	}
	for(int i=1; i<=n; i++){
		if(!mark[i]){
			dfs(i);
		}
	}
	reverse(all(toposorted));
	for(int v : toposorted){
		for(auto to = revadj[v].begin(); to!=revadj[v].end(); to++){
			int nd=*to;
			if(d[nd]+1>=d[v]){
				d[v]=d[nd]+1;
				p[v]=nd;
			}
		}
	}
}

void solve(){
	int n, m;
	cin >> n >> m;
	for(int i=0; i< m; i++){
		int x, y;
		cin >> x >> y;
		adj[x].insert(y);
		revadj[y].insert(x);
	}
	int ans=-1;
	bool ok;
	while(true){
		prevans=max(prevans, ans);
		ok=0;
		toposorted.clear();
		sortbydist(n);
		int mx=0;
		int mxind=0;
		for(int i=1; i<=n; i++){
			if(d[i]>=mx){
				mx=d[i];
				mxind=i;
			}
		}
		vector<int> path;
		while(p[mxind]!=0){
			path.pb(mxind);
			mxind=p[mxind];
		}
		if(path.size()<=prevans){
			cout << "! " << prevans << endl;
			return;
		}
		reverse(all(path));
		for(int i=0; i< path.size(); i++){
			bool yes;
			if(!asked[{mxind, path[i]}]){
				cout << "? " << mxind << " " << path[i] << endl;
				cin >> yes;
				asked[{mxind, path[i]}]=1;
			}
			else yes=1;
			if(!yes){
				ans=i;
				adj[mxind].erase(path[i]);
				revadj[path[i]].erase(mxind);
				ok=1;
				break;
			} 
			mxind=path[i];
 		}
 		if(!ok){
 			prevans=path.size();
 			break;
 		}
	}
	cout << "! " << prevans << endl;
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}