#include <bits/stdc++.h>
using namespace std;
int query(vector<int> nodes); // provided by grader
vector<vector<int>> g;
vector<bool> vis;
void collect(int u, vector<int>& comp) {
vis[u] = true;
comp.push_back(u);
for (int v : g[u]) {
if (!vis[v]) collect(v, comp);
}
}
vector<int> get_connected_subset(const vector<int>& from, int need) {
unordered_set<int> in(from.begin(), from.end());
vis.assign(g.size(), true); // block everything
for (int x : from) vis[x] = false;
vector<int> result;
for (int u : from) {
if (!vis[u]) {
vector<int> tmp;
collect(u, tmp);
for (int x : tmp) result.push_back(x);
if ((int)result.size() >= need) {
result.resize(need);
return result;
}
}
}
return result;
}
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 ((int)remaining.size() > 1) {
int half = remaining.size() / 2;
vector<int> part = get_connected_subset(remaining, half);
if (query(part)) {
remaining = part;
} else {
// use rest = remaining - part
unordered_set<int> in_part(part.begin(), part.end());
vector<int> rest;
for (int x : remaining) {
if (!in_part.count(x)) rest.push_back(x);
}
// Ensure rest is connected: attach it to part if needed
vector<int> new_query = get_connected_subset(rest, min((int)rest.size(), half));
for (int x : part) new_query.push_back(x); // attach to ensure connected
if (query(new_query)) {
remaining.clear();
unordered_set<int> in_new(new_query.begin(), new_query.end());
for (int x : rest) {
if (in_new.count(x)) remaining.push_back(x);
}
} else {
// Egg is not in rest → stay in part
remaining = part;
}
}
}
return remaining[0];
}
