#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();
}
