#include <bits/stdc++.h>
#define ll long long
#define MAXN 50010
#define MAXM 100010
using namespace std;
vector<pair<ll,ll> > G[MAXN];
bool active[MAXM];
ll n,indeg[MAXN];
pair<ll,ll> len[MAXN];
vector<ll> Longest_Path()
{
    for (ll i=1;i<=n;i++)
    {
        len[i]={-1,0};
        for (auto j : G[i])
        {
            if (active[j.second])
                indeg[j.first]++;
        }
    }
    queue<ll> q;
    for (ll i=1;i<=n;i++)
    {
        if (!indeg[i])
        {
            len[i]={0,0};
            q.push(i);
        }
    }
    ll maxx=1,pos=0;
    while (!q.empty())
    {
        ll i=q.front();
        if (len[i].first>maxx)
        {
            maxx=len[i].first;
            pos=i;
        }
        q.pop();
        for (auto next : G[i])
        {
            if (active[next.second])
            {
                indeg[next.first]--;
                if (len[i].first+1>len[next.first].first)
                    len[next.first]={len[i].first+1,i};
                if (!indeg[next.first])
                    q.push(next.first);
            }
        }
    }
    vector<ll> ans;
    ans.push_back(pos);
    while (len[pos].first)
    {
        pos=len[pos].second;
        ans.push_back(pos);
    }
    reverse(ans.begin(),ans.end());
    return ans;
}
map<pair<ll,ll>,ll> ind;
int main()
{
    ll m,u,v;
    cin >> n >> m;
    for (ll i=1;i<=m;i++)
    {
        cin >> u >> v;
        G[u].push_back({v,i});
        active[i]=true;
        ind[{u,v}]=i;
    }
    ll c;
    while (true)
    {
        bool yes=true;
        vector<ll> v=Longest_Path();
        if (v.size()==1)
        {
            cout << "! " << 0 << "\n";
            return 0;
        }
        for (ll i=0;i<v.size()-1;i++)
        {
            cout << v[i] << " " << v[i+1] << "\n";
            cin >> c;
            if (!c)
            {
                yes=false;
                active[ind[{v[i],v[i+1]}]]=false;
                break;
            }
        }
        if (yes)
        {
            cout << "! " << v.size()-1 << "\n";
            return 0;
        }
    }
    return 0;
}