#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=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,m;
while(r-l>1)
{
m=(l+r)/2;
vector<int> v1;
for(int i=l;i<m;i++)
{
v1.push_back(tops[i]);
}
if(query(v1)==1)
{
r=m;
}
else
{
l=m+1;
}
}
return l;
}
