#include <vector>
#include <utility>
#include "grader.h"
#define MAX_N 513
#define MAX_M (2*MAX_N)
int head[MAX_N], vv[MAX_M], nxt[MAX_M], eo,timer,tin[MAX_N],aux[MAX_N];
void link(int u,int v)
{
int i=++eo;
nxt[i]=head[u],vv[i]=v;
head[u]=i;
}
void dfs(int u,int p)
{
aux[tin[u]=timer++]=u;
for(int j=head[u];j;j=nxt[j])if(p-vv[j])dfs(vv[j],u);
}
int findEgg(int n,std::vector<std::pair<int, int> >bridges)
{
for(int i=1;i<=n;++i)head[i]=eo=timer=0;
for(auto[u,v]:bridges)link(u,v),link(v,u);
dfs(1,1);
int lower=-1,upper=n;
while(upper-lower>1)
{
int mid=lower+(upper-lower)/2;
std::vector<int>q;
for(int i=0;i<=mid;++i)q.push_back(aux[i]);
if(query(q))upper=mid;
else lower=mid;
}
return aux[upper];
}
/* int query(std::vector<int> islands) */
