#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]) v.emplace_back(u), ct++; 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); } } } return *cur.begin(); }