#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<int>v1[1024];
int used[1024];
vector<int>eu;
void DFS(int beg)
{
used[beg]=1;
int nb;
eu.push_back(beg);
for(int i=0;i<v1[beg].size();i++)
{
nb=v1[beg][i];
if(!used[nb])
{
DFS(nb);
}
}
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
int n=N;
for(int i=1;i<=N;i++)v1[i].clear();
eu.clear();
eu.push_back(0);
memset(used,0,sizeof(used));
for(int i=0;i<bridges.size();i++)
{
v1[bridges[i].first].push_back(bridges[i].second);
v1[bridges[i].second].push_back(bridges[i].first);
}
DFS(1);
int l=1;
int r=n;
vector<int>b1;
vector<int>b2;
int mid;
while(l<r)
{
mid=(l+r)/2;
for(int i=1;i<=mid;i++)
{
b1.push_back(eu[i]);
}
if(query(b1)==true)r=mid;
else l=mid+1;
b1.clear();
}
return eu[r];
}
