#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
const int N=2*1e4+50;
vector<pair<int,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(i.se==1 && !was[i.fi])DFS(i.fi);
    }
    topo.pb(u);
}
void DFSclear(int u)
{
    was[u]=false;
    for(auto i:E[u])
    {
        if(i.se==1)DFSclear(i.fi);
    }
}
int ask(int u,int v)
{
    cout<<"? "<<u<<" "<<v<<endl;
    int x;cin>>x;
    return x;
}
int main()
{
    int n,m;cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;cin>>u>>v;
        E[u].pb({v,1});
        E1[v].pb({u,1});
    }
    int res;
    while(1)
    {
        for(int i=1;i<=n;i++)
        {
            int ct=0;
            for(auto j:E1[i])
            {
                if(j.se==1) ct++;
            }
            if(ct==0)
            {
                //cout<<i<<endl;
                DFS(i);
                DFSclear(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(k.se==1 && dp[k.fi]+1>dp[u]){dp[u]=max(dp[u],dp[k.fi]+1);parent[u]=k.fi;}
                    }
                }
                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))
            {
                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]=0;
    }
    cout<<res<<endl;
    return 0;
}