#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(int i=0; i<n-1; i++)
{
v[bridges[i].first].push_back(bridges[i].second);
v[bridges[i].second].push_back(bridges[i].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-1;
else l=mid+1;
}
return r+1;
}
