#include <bits/stdc++.h>
using namespace std;
int query(vector<int> nodes); // external
vector<vector<int>> g;
vector<bool> removed;
int compute_subtree_sizes(int u, int p, vector<int>& sz, const vector<int>& available) {
sz[u] = 1;
for (int v : g[u]) {
if (v != p && !removed[v] && binary_search(available.begin(), available.end(), v)) {
sz[u] += compute_subtree_sizes(v, u, sz, available);
}
}
return sz[u];
}
void collect_nodes(int u, int p, vector<int>& nodes) {
nodes.push_back(u);
for (int v : g[u]) {
if (v != p && !removed[v]) {
collect_nodes(v, u, nodes);
}
}
}
int findEgg(int n, vector<pair<int, int>> edges) {
g.assign(n + 1, {});
removed.assign(n + 1, false);
for (auto [u, v] : edges) {
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> available(n);
iota(available.begin(), available.end(), 1);
sort(available.begin(), available.end()); // for binary_search in subtree size calculation
while (available.size() > 1) {
int root = available[0];
vector<int> sz(n + 1, 0);
compute_subtree_sizes(root, 0, sz, available);
int total_size = sz[root];
int found = -1;
for (int v : g[root]) {
if (removed[v]) continue;
if (!binary_search(available.begin(), available.end(), v)) continue;
vector<int> sub;
collect_nodes(v, root, sub);
if ((int)sub.size() * 2 >= total_size) { // roughly half or more
if (query(sub)) {
removed[root] = true;
available = sub;
} else {
for (int x : sub) removed[x] = true;
vector<int> new_available;
for (int x : available) {
if (!removed[x]) new_available.push_back(x);
}
available = new_available;
}
found = 1;
break;
}
}
if (found == -1) {
// no child was large enough, query the rest (root itself)
if (query({root})) {
return root;
} else {
removed[root] = true;
vector<int> new_available;
for (int x : available) {
if (!removed[x]) new_available.push_back(x);
}
available = new_available;
}
}
}
return available[0];
}
