#include <bits/stdc++.h>
using namespace std;
int query(vector<int> nodes); // Provided externally
vector<vector<int>> g;
vector<bool> used;
vector<int> subtree;
void collect(int u, int p) {
subtree.push_back(u);
used[u] = true;
for (int v : g[u]) {
if (!used[v] && v != p) {
collect(v, u);
}
}
}
int findEgg(int n, vector<pair<int, int>> edges) {
g.assign(n + 1, {});
used.assign(n + 1, false);
for (auto [u, v] : edges) {
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> curr;
curr.push_back(1);
// Expand to full connected component
used.assign(n + 1, false);
subtree.clear();
collect(1, -1);
curr = subtree;
while (curr.size() > 1) {
// Try to extract a connected component of roughly half the size
vector<bool> mark(n + 1, false);
for (int x : curr) mark[x] = true;
used.assign(n + 1, false);
vector<int> half;
for (int u : curr) {
if (!used[u]) {
subtree.clear();
collect(u, -1);
if (subtree.size() <= curr.size() / 2) {
for (int x : subtree) half.push_back(x);
if (half.size() >= curr.size() / 2) break;
}
}
}
// if half not big enough, add nodes from current to make it big and connected
if (half.size() < curr.size() / 2) {
for (int x : curr) {
if (find(half.begin(), half.end(), x) == half.end()) {
half.push_back(x);
if (half.size() >= curr.size() / 2) break;
}
}
}
if (query(half)) {
curr = half;
} else {
vector<int> other;
for (int x : curr) {
if (find(half.begin(), half.end(), x) == half.end()) {
other.push_back(x);
}
}
curr = other;
}
}
return curr[0];
}
