#include <bits/stdc++.h>
using namespace std;
int query(vector<int> nodes); // Provided externally
vector<vector<int>> g;
vector<bool> visited;
vector<int> subtree;
void collect(int u) {
visited[u] = true;
subtree.push_back(u);
for (int v : g[u]) {
if (!visited[v]) {
collect(v);
}
}
}
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> current;
// Step 1: Start with a full traversal from node 1
visited.assign(n + 1, false);
subtree.clear();
collect(1);
current = subtree;
while (current.size() > 1) {
// Step 2: Try to extract a connected half from current
visited.assign(n + 1, false);
vector<int> half;
queue<int> q;
// Start from any node in current
q.push(current[0]);
visited[current[0]] = true;
unordered_set<int> currentSet(current.begin(), current.end());
half.push_back(current[0]);
while (!q.empty() && half.size() < current.size() / 2) {
int u = q.front(); q.pop();
for (int v : g[u]) {
if (!visited[v] && currentSet.count(v)) {
visited[v] = true;
q.push(v);
half.push_back(v);
if (half.size() >= current.size() / 2) break;
}
}
}
// Step 3: Query the half
if (query(half)) {
current = half;
} else {
unordered_set<int> halfSet(half.begin(), half.end());
vector<int> other;
for (int x : current) {
if (!halfSet.count(x)) other.push_back(x);
}
current = other;
}
}
return current[0];
}
