#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
const int maxn = 520, oo = 1e9;
int n;
vector<int> adj[maxn];
bool era[maxn];
int dak, cur, cup;
int findEgg (int N, vector<pair<int,int> > bridges)
{
memset(era, 0, sizeof era);
::n = N;
for (int i = 1; i <= n; i++) adj[i].clear();
for (pair<int,int> p : bridges) {
adj[p.first].push_back(p.second);
adj[p.second].push_back(p.first);
}
vector<int> rem(n);
iota(rem.begin(), rem.end(), 1);
while ((int)rem.size() > 1) {
auto DFS = [&] (auto DFS, int u, int par) -> int
{
int cnt = 1;
for (int v : adj[u]) {
if (era[v]) continue;
if (v == par) continue;
cnt += DFS(DFS, v, u);
}
if (abs(dak - (int)rem.size() / 2) > abs(cnt - (int)rem.size() / 2)) {
dak = cnt;
cur = u;
cup = par;
}
return cnt;
};
dak = oo;
for (int x : rem) {
DFS(DFS, x, -1);
}
vector<int> tmp;
auto DFSadd = [&] (auto DFSadd, int u, int par) -> void
{
tmp.push_back(u);
for (int v : adj[u]) {
if (era[v]) continue;
if (v != par) DFSadd(DFSadd, v, u);
}
};
DFSadd(DFSadd, cur, cup);
sort(tmp.begin(), tmp.end());
if (!query(tmp)) {
for (int x : tmp) era[x] = true;
vector<int> newrem;
for (int x : rem) {
if (!era[x]) newrem.push_back(x);
}
swap(rem, newrem);
}
else {
for (int x : rem) {
if (!binary_search(tmp.begin(), tmp.end(), x)) era[x] = true;
}
swap(rem, tmp);
}
}
return rem[0];
}
