感觉很神奇啊，想了挺久的。
如果没有粉色边是容易的。竞赛图中，强连通分量缩点后，拓扑序较小的点向每一个拓扑序比它大的点连边。
利用这个性质，我们维护一个答案集合 \(S\)，当 \(|S| \ge 2\) 时，每次随意取出两个点 \(u, v \in S\)。如果边的方向是 \(u \to v\) 那么删掉 \(v\)，否则删掉 \(u\)。
正确性显然。如果 \(u, v\) 不在同一个强连通分量，那我们保留了拓扑序较小的强连通分量中的点；如果在，我们随机保留一个就好了。直到 \(|S| = 1\) 时，剩下的唯一点就是在拓扑序最小的强连通分量中。
有粉色边的情况，我们先把粉色边构成的强连通分量缩起来，从入度为 \(0\) 的分量中随便取一个点组成初始的 \(S\)。仍然是做一遍上面的流程，只不过删除一个点时把它入度为 \(0\) 的后继加入 \(S\)。
这样的话，如果我们最后选的点是通过前驱被删掉而加入 \(S\) 的，那它一定能通过绿色边走到它的前驱。它的后继通过粉色边也能走到。如果最后选的点原来没有粉色边相连，由于我们询问的方式，它能只走绿色边到达全部点（感性理解）。
具体实现时可以不需要 Tarjan，类似拓扑排序删除一些构成环的边即可。
由于每次询问都会从 \(S\) 中删除一个点，所以询问次数 \(\le n - 1\)。
code
// Problem: E. Pink Floyd
// Contest: Codeforces - Codeforces Round 549 (Div. 1)
// URL: https://codeforces.com/problemset/problem/1142/E
// Memory Limit: 256 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 100100;
int n, m, ind[maxn];
bool vis[maxn], siv[maxn];
vector<int> G[maxn], T[maxn];
void dfs(int u) {
vis[u] = siv[u] = 1;
for (int v : T[u]) {
if (!siv[v]) {
G[u].pb(v);
++ind[v];
}
if (!vis[v]) {
dfs(v);
}
}
siv[u] = 0;
}
inline int ask(int x, int y) {
printf("? %d %d\n", x, y);
fflush(stdout);
scanf("%d", &x);
return x;
}
void solve() {
scanf("%d%d", &n, &m);
while (m--) {
int u, v;
scanf("%d%d", &u, &v);
T[u].pb(v);
}
for (int i = 1; i <= n; ++i) {
if (!vis[i]) {
dfs(i);
}
}
vector<int> S;
for (int i = 1; i <= n; ++i) {
if (!ind[i]) {
S.pb(i);
}
}
while ((int)S.size() > 1) {
int u = *(--S.end()), v = *(----S.end());
if (ask(u, v)) {
S.erase(----S.end());
for (int w : G[v]) {
if (!(--ind[w])) {
S.pb(w);
}
}
} else {
S.erase(--S.end());
for (int w : G[u]) {
if (!(--ind[w])) {
S.pb(w);
}
}
}
}
printf("! %d\n", S[0]);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}