#include <bits/stdc++.h>
using namespace std;
int query(vector<int> nodes); // Provided externally
vector<vector<int>> g;
vector<bool> removed;
vector<int> sizes;
void dfs_size(int u, int p) {
sizes[u] = 1;
for (int v : g[u]) {
if (v != p && !removed[v]) {
dfs_size(v, u);
sizes[u] += sizes[v];
}
}
}
int find_centroid(int u, int p, int total) {
for (int v : g[u]) {
if (v != p && !removed[v] && sizes[v] > total / 2) {
return find_centroid(v, u, total);
}
}
return u;
}
void collect_subtree(int u, int p, vector<int>& result) {
result.push_back(u);
for (int v : g[u]) {
if (v != p && !removed[v]) {
collect_subtree(v, u, result);
}
}
}
int decompose(int root) {
dfs_size(root, -1);
int total = sizes[root];
int centroid = find_centroid(root, -1, total);
removed[centroid] = true;
for (int v : g[centroid]) {
if (!removed[v]) {
vector<int> subtree;
collect_subtree(v, centroid, subtree);
if (query(subtree)) {
return decompose(v);
}
}
}
return centroid;
}
int findEgg(int n, vector<pair<int, int>> edges) {
g.assign(n + 1, {});
removed.assign(n + 1, false);
sizes.assign(n + 1, 0);
for (auto [u, v] : edges) {
g[u].push_back(v);
g[v].push_back(u);
}
return decompose(1);
}
