#include <bits/stdc++.h>
using namespace std;
int query(vector<int> nodes); // provided externally
vector<vector<int>> g;
vector<int> get_connected(const vector<int>& from, int want) {
unordered_set<int> in(from.begin(), from.end());
vector<bool> vis(g.size(), false);
vector<int> result;
queue<int> q;
for (int x : from) {
q.push(x);
vis[x] = true;
break;
}
while (!q.empty() && (int)result.size() < want) {
int u = q.front(); q.pop();
if (!in.count(u)) continue;
result.push_back(u);
for (int v : g[u]) {
if (!vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
return result;
}
int findEgg(int n, vector<pair<int, int>> edges) {
g.assign(n + 1, {});
for (auto [u, v] : edges) {
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> remaining(n);
iota(remaining.begin(), remaining.end(), 1);
while ((int)remaining.size() > 1) {
int sz = remaining.size();
int half = sz / 2;
vector<int> a = get_connected(remaining, half);
unordered_set<int> in_a(a.begin(), a.end());
if (query(a)) {
remaining = a;
} else {
vector<int> b;
for (int x : remaining)
if (!in_a.count(x)) b.push_back(x);
vector<int> comp_b = get_connected(b, half);
vector<int> query_set = comp_b;
for (int i = 0; i < (int)a.size() && query_set.size() < half * 2; ++i)
query_set.push_back(a[i]); // attach to ensure connectedness
if (query(query_set)) {
unordered_set<int> in_comp_b(comp_b.begin(), comp_b.end());
vector<int> next;
for (int x : query_set)
if (in_comp_b.count(x)) next.push_back(x);
remaining = next;
} else {
remaining = a;
}
}
}
return remaining[0];
}
