#include <bits/stdc++.h> #include "grader.h" using namespace std; const int maxN = 515; int N; vector<int> adj[maxN]; set<int> cur; bool del[maxN]; queue<pair<int,int>> q; // u, pa int findEgg (int n, vector<pair<int,int>> bridges) { N = n; for (auto [u, v] : bridges) { adj[u].emplace_back(v); adj[v].emplace_back(u); } for (int i = 1; i <= N; i++) { cur.insert(i); } while (cur.size() != 1) { int left = cur.size(); int need = left / 2; int ct = 0; vector<int> v; q.push({*cur.begin(), -1}); while (!q.empty()) { auto [u, pa] = q.front(); q.pop(); if (ct >= need) continue; if (!del[u]) ct++; v.emplace_back(u); for (auto vv : adj[u]) { if (vv == pa) continue; q.emplace(vv, u); } } bool ok = query(v); if (ok) { set<int> have; for (auto x : v) { if (!del[x]) have.insert(x); } for (auto x : cur) { if (have.find(x) == have.end()) { del[x] = 1; } } cur = have; } else { for (auto x : v) { del[x] = 1; if (cur.find(x) != cur.end()) cur.erase(x); } } } int ans = *cur.begin(); cur.clear(); memset(del, 0, sizeof del); while (!q.empty()) q.pop(); for (int i = 0; i < maxN; i++) adj[i].clear(); return ans; }