#include <bits/stdc++.h>
using namespace std;

#ifdef CKISEKI
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
template <typename ...T>
void debug_(const char *s, T ...a) {
    cerr << "\e[1;32m(" << s << ") = (";
    int cnt = sizeof...(T);
    (..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char *s, I L, I R) {
    cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L)
        cerr << (f++ ? ", " : "") << *L;
    cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

constexpr int kN = 50000 + 5;

unordered_set<int> g[kN];
int step[kN], stepc;
int dp[kN];

int go(int u) {
    if (step[u] == stepc)
        return dp[u];
    dp[u] = 0;
    step[u] = stepc;
    for (int v : g[u])
        dp[u] = max(dp[u], go(v) + 1);
    return dp[u];
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].insert(v);
    }
    while (true) {
        stepc++;
        pair<int, int> best = {0, 0};
        for (int i = 1; i <= n; ++i)
            best = max(best, {go(i), i});
        int x = best.second;
        vector<int> path = {x};
        while (dp[x] > 0) {
            for (int y : g[x]) {
                if (dp[x] == dp[y] + 1) {
                    path.push_back(x = y);
                    break;
                }
            }
        }

        bool good = true;
        for (size_t i = 1; i < path.size(); ++i) {
            int u = path[i - 1];
            int v = path[i];
            printf("? %d %d\n", u, v);
            fflush(stdout);
            int exist;
            scanf("%d", &exist);
            if (not exist) {
                g[u].erase(v);
                good = false;
                break;
            }
        }

        if (good) {
            printf("! %d\n", int(path.size()) - 1);
            break;
        }
    }
    return 0;
}