#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define int long long
const int N=2*1e4+50;
map<pair<int,int>,int>mapa;
vector<int>E[N],E1[N];
int dp[N],parent[N];
bool was[N];
vector<int>topo;
void DFS(int u)
{
    /*for(auto i:E1[u])
    {
        if(i.se==1 && dp[i.fi]+1>dp[u]){dp[u]=max(dp[u],dp[i.fi]+1);parent[u]=i.fi;}
    }*/
    was[u]=true;
    for(auto i:E[u])
    {
        if(mapa[{u,i}] && !was[i])DFS(i);
    }
    topo.pb(u);
}
int ask(int u,int v)
{
    cout<<"? "<<u<<" "<<v<<endl;
    int x;cin>>x;
    return x;
}
signed main()
{
    int n,m;cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;cin>>u>>v;
        E[u].pb(v);
        E1[v].pb(u);
        mapa[{u,v}]=1;
        mapa[{v,u}]=1;
    }
    /*for(int i=1;i<=n;i++)
    {
        sort(E[i].begin(),E[i].end());
        sort(E1[i].begin(),E1[i].end());
    }*/
    int res;
    while(1)
    {
        for(int i=1;i<=n;i++)
        {
            int ct=0;
            for(auto j:E1[i])
            {
                if(mapa[{i,j}]==1) ct++;
            }
            if(ct==0)
            {
                //cout<<i<<endl;
                DFS(i);
                reverse(topo.begin(),topo.end());
                /*for(auto j:topo)cout<<j<<" ";
                cout<<endl;*/
                for(int j=1;j<topo.size();j++)
                {
                    int u=topo[j];
                    for(auto k:E1[u])
                    {
                        if(mapa[{u,k}] && dp[k]+1>dp[u]){dp[u]=max(dp[u],dp[k]+1);parent[u]=k;}
                    }
                }
                topo.clear();
            }
        }
        /*for(int i=1;i<=n;i++)cout<<dp[i]<<" ";
        cout<<endl;
        for(int i=1;i<=n;i++)cout<<parent[i]<<" ";
        cout<<endl;*/
        int ind=1;
        for(int i=1;i<=n;i++)
        {
            if(dp[i]>dp[ind])ind=i;
        }
        vector<int>put;
        int par=parent[ind];
        do
        {
            put.pb(ind);
            ind=par;
            par=parent[par];
        }while(par!=0);
        put.pb(ind);
        bool bul=false;
        /*for(auto i:put)cout<<i<<" ";
        cout<<endl;*/
        for(int i=put.size()-1;i>=1;i--)
        {
            int u=put[i],v=put[i-1];
            if(!ask(u,v))
            {
                mapa[{u,v}]=0;
                mapa[{v,u}]=0;
                /*int l=0,r=E[u].size()-1,mid=(l+r)/2,lb;
                while(l<=r)
                {
                    if(E[u][mid].fi<=v)
                    {
                        lb=mid;
                        l=mid+1;
                    }
                    else r=mid-1;
                    mid=(l+r)/2;
                }
                E[u][lb].se=0;
                l=0,r=E1[v].size()-1,mid=(l+r)/2;
                while(l<=r)
                {
                    if(E1[v][mid].fi<=u)
                    {
                        lb=mid;
                        l=mid+1;
                    }
                    else r=mid-1;
                    mid=(l+r)/2;
                }
                E1[v][lb].se=0;*/
                /*int lb=lower_bound(E[u].begin(),E[u].end(),v)-E[u].begin();
                E[u][lb].se=0;
                lb=lower_bound(E1[v].begin(),E1[v].end(),u)-E1[v].begin();
                E[v][lb].se=0;*/
                /*for(auto &j:E[u])
                {
                    if(j.fi==v) j.se=0;
                }*/
                /*for(auto &j:E1[v])
                {
                    if(j.fi==u) j.se=0;
                }*/
                bul=true;
                break;
            }
        }
        if(!bul){res=put.size()-1;break;}
        for(int i=1;i<=n;i++)dp[i]=parent[i]=was[i]=0;
    }
    cout<<"! "<<res<<endl;
    return 0;
}