#include "grader.h"
#include <iostream>
#include <vector>
using namespace std;
int used[1024];
vector <int> v[1024];
vector <int> ans;
void dfs(int beg)
{
used[beg]=1;
ans.push_back(beg);
for(auto c:v[beg])
{
if(!used[c])
{
dfs(c);
}
}
return;
}
int findEgg(int N, vector < pair < int, int > > bridges)
{
fill(used,used+1000,0);
ans.clear();
for(int i=1;i<=1010;i++)
{
v[i].clear();
}
for(auto c:bridges)
{
v[c.first].push_back(c.second);
v[c.second].push_back(c.first);
}
dfs(1);
int l=1;
int r=N;
int mid;
bool la;
while(l<=r)
{
mid=(l+r)/2;
vector <int>k;
for(int i=mid;i<=r;i++)
{
k.push_back(ans[i]);
}
la=query(k);
if(la)
{
l=mid+1;
}
else r=mid-1;
}
return ans[l];
}
