#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
using namespace std;
typedef long long ll;
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) int(a.size())
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
// External function provided by the problem
int query(vector<int> islands);
vvi g;
vi ak;
int mid;
int ile_poszlo;
vi pyt;
void dfs_pyt(int v, int p) {
if (ile_poszlo >= mid) return;
if (ak[v]) {
ile_poszlo++;
}
pyt.pb(v);
for (int u : g[v]) {
if (u == p) continue;
dfs_pyt(u, v);
}
}
int findEgg(int n, vector<pii> kr) {
g.assign(n + 1, vi());
for (auto [u, v] : kr) {
g[u].pb(v);
g[v].pb(u);
}
ak.assign(n + 1, 1); // 1 if potential suspect
unordered_set<int> zb;
for (int i = 1; i <= n; ++i) zb.insert(i);
while (sz(zb) > 1) {
mid = sz(zb) / 2;
pyt.clear();
ile_poszlo = 0;
// Start from an arbitrary suspect
dfs_pyt(*zb.begin(), 0);
int val = query(pyt);
if (val) {
// Collect old suspects in pyt BEFORE resetting ak
unordered_set<int> lol;
for (int ele : pyt) {
if (ak[ele]) {
lol.insert(ele);
}
}
// Reset ak
for (int i = 1; i <= n; ++i) ak[i] = 0;
// Set new ak and zb
for (int ele : lol) ak[ele] = 1;
zb = move(lol);
} else {
for (int ele : pyt) {
if (ak[ele]) {
zb.erase(ele);
ak[ele] = 0;
}
}
}
// Removed the unnecessary loop here
}
return *zb.begin();
}
