#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define pb push_back
template<class _,class __>
bool minimize(_ & a,const __ b) {
if (a > b) {
a = b;
return true;
}
return false;
}
const int MaxN = 555;
int n,Tin[MaxN],Tout[MaxN],sz[MaxN],rot,delta;
bool isDel[MaxN];
vector<int> a[MaxN];
void dfs(int u,int p) {
Tin[u] = ++Tin[0];
sz[u] = 1;
for (int v : a[u]) {
if (isDel[v] || v == p) continue;
dfs(v,u);
sz[u] += sz[v];
}
Tout[u] = Tin[0];
}
void dfss(int u,int p,int r) {
for (int v : a[u]) {
if (v == p || isDel[v]) continue;
if (minimize(delta,abs(sz[v] - (sz[r] - sz[v])))) rot = v;
dfss(v,u,r);
}
}
bool isPar(int u,int v) {
return Tin[u] <= Tin[v] && Tout[v] <= Tout[u];
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
// if (query ({1})) return 1;
// return N;
n = N;
for(pair<int,int> tmp : bridges) {
int u = tmp.first;
int v = tmp.second;
a[u].pb(v);
a[v].pb(u);
}
Tin[0] = 0;
for(int i=1;i<=N;i++) {
isDel[i] = false;
}
int root;
while(true) {
for(int i=1;i<=n;i++) {
if (isDel[i]) continue;
root = i;
dfs(i,-1);
break;
}
if(sz[root] == 1) break;
delta = 1e9;
dfss(root,-1,root);
vector<int> tmp;
for(int i=1;i<=n;i++) {
if (!isDel[i] && isPar(rot,i)) tmp.pb(i);
}
if (query(tmp)) {
for (int i=1;i<=n;i++) if (!isPar(rot,i)) isDel[i] = true;
}
else for(int i=1;i<=n;i++) if (isPar(rot,i)) isDel[i] = true;
}
for (int i=1;i<=N;i++) a[i].clear();
return root;
}
