#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
const int M=1e5+10;
int n,m,x,y;
vector<pair<int,int>>e[N];
int deg[N],dis[N],c[M],a[M],b[M],bk[N];
vector<int> findpath(){
	for (int i=1;i<=n;i++) dis[i]=deg[i]=bk[i]=0;
	for (int i=1;i<=m;i++)if (!c[i]){
		deg[b[i]]++;
	}
	queue<int>q;
	for (int i=1;i<=n;i++) if (!deg[i]) q.push(i);
	while (!q.empty()){
		int t=q.front(); q.pop();
		for (int i=0;i<e[t].size();i++){
			int u=e[t][i].first;
			int id=e[t][i].second;
			if (c[id]) continue;
			deg[u]--;
			if (dis[u]<dis[t]+1){
				dis[u]=dis[t]+1;
				bk[u]=id;
			}
			if (deg[u]==0){
				q.push(u);
			}
		}
	}
	int pos=1;
	for (int i=2;i<=n;i++)
		if (dis[pos]<dis[i]){
			pos=i;
		}
	vector<int>t;
	while (bk[pos]){
		t.push_back(bk[pos]);
		pos=a[bk[pos]];
	}
	return t;
}
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++){
		scanf("%d%d",&a[i],&b[i]);
		e[a[i]].push_back(make_pair(b[i],i));
	}
	while (1){
		vector<int>s=findpath();
		int flag=1;
		for (int i=0;i<s.size();i++){
			printf("? %d %d\n",a[s[i]],b[s[i]]);
			fflush(stdout);
			int x;
			scanf("%d",&x);
			if (!x){
				flag=0;
				c[s[i]]=1;
				break;
			}
		}
		if (flag){
			printf("! %d\n",(int)s.size());
			fflush(stdout);
			return 0;
		}
	}
}