#include <bits/stdc++.h>

using namespace std;

const int N = 5e4 + 10;
int n, m;
set<int> g[N];
int dp[N];
bool mark[N];
vector<int> path;

int ask(int u, int v) {
    cout << "? " << u << " " << v << endl;
    int x;
    cin >> x;
    return x;
}

void dfs(int u) {
    if(mark[u]) return;
    mark[u] = true;
    for(int v : g[u]) {
        if(mark[v]) {
            dp[u] = max(dp[u], dp[v] + 1);
            continue;
        }
        dfs(v);
        dp[u] = max(dp[u], dp[v] + 1);
    }
}

void dfs2(int u) {
    path.push_back(u);
    for(int v : g[u]) {
        if(dp[v] == dp[u] - 1) {
            dfs2(v);
            break;
        }
    }
}

int main() {
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].insert(v);
    }
    while(true) {
        for(int i = 1; i <= n; i++) {
            mark[i] = false;
            dp[i] = 0;
        }
        for(int i = 1; i <= n; i++) {
            if(mark[i]) continue;
            dfs(i);
        }
        path.clear();
        int mx = 1;
        for(int i = 2; i <= n; i++) if(dp[i] > dp[mx]) mx = i;
        dfs2(mx);
        bool ok = true;
        for(int i = 1; i < path.size(); i++) {
            if(ask(path[i - 1], path[i]) == 0) {
                g[path[i - 1]].erase(path[i]);
                ok = false;
                break;
            }
        }
        if(ok) {
            cout << "! " << path.size() - 1;
            return 0;
        }
    }
    return 0;
}