#include <vector>
#include "grader.h"
using namespace std;
int used[520];
vector<int>in;
vector<int>v[520];
void DFS(int beg)
{
used[beg]=1;
in.push_back(beg);
for(int nb:v[beg])
{
if(!used[nb])DFS(nb);
}
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
int n=N;
for(int i=1; i<=n; i++)
{
v[i].clear();
used[i]=0;
}
in.clear();
for(pair<int,int> c:bridges)
{
v[c.first].push_back(c.second);
v[c.second].push_back(c.first);
}
DFS(1);
int r=n,l=1;
vector<int>pref;
while(l<r)
{
pref.clear();
int mid=(l+r)/2;
for(int i=1; i<=mid; i++)pref.push_back(in[i-1]);
if(query(pref)==1)r=mid;
else l=mid+1;
}
return in[r-1];
}
