#include <bits/stdc++.h>
using namespace std;
int query(vector<int> nodes);
vector<vector<int>> g;
vector<bool> blocked;
vector<int> get_component(const vector<int>& from, int want_size) {
unordered_set<int> in(from.begin(), from.end());
vector<int> comp;
vector<bool> vis(g.size(), false);
queue<int> q;
for (int x : from) {
q.push(x);
vis[x] = true;
break;
}
while (!q.empty() && (int)comp.size() < want_size) {
int u = q.front(); q.pop();
if (!in.count(u)) continue;
comp.push_back(u);
for (int v : g[u]) {
if (!vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
return comp;
}
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 (remaining.size() > 1) {
int half = remaining.size() / 2;
vector<int> a = get_component(remaining, half);
if (query(a)) {
remaining = a;
} else {
unordered_set<int> in_a(a.begin(), a.end());
vector<int> rest;
for (int x : remaining) {
if (!in_a.count(x)) rest.push_back(x);
}
vector<int> b = get_component(rest, half);
vector<int> b_query = b;
unordered_set<int> b_set(b.begin(), b.end());
for (int x : a) {
if ((int)b_query.size() >= half) break;
if (!b_set.count(x)) b_query.push_back(x);
}
if (query(b_query)) {
remaining = b;
} else {
remaining = a;
}
}
}
return remaining[0];
}
