#include<bits/stdc++.h>
#include"grader.h"
using namespace std;
vector<int> v[1000],tops;
int used[1000];
void DFS(int i)
{
tops.push_back(i);
used[i]=1;
int sz=v[i].size(),nb;
for(int j=0;j<sz;j++)
{
nb=v[i][j];
if(used[nb]==0)
{
DFS(nb);
}
}
}
int findEgg(int n, vector < pair < int, int > > bridges)
{
for(int i=1;i<=n;i++)
{
v[i].clear();
used[i]=0;
}
tops.clear();
for(int i=0;i<n;i++)
{
v[bridges[i].first].push_back(bridges[i].second);
v[bridges[i].second].push_back(bridges[i].first);
}
DFS(1);
int l=0,r=n-1,m;
vector<int> v1;
while(l < r)
{
m = l + (r - l)/2;
v1.clear();
for(int i=0;i<=m;i++)
{
v1.push_back(tops[i]);
}
if(query(v1))
{
r=m;
}
else
{
l=m+1;
}
}
return tops[r];
}
