#include <bits/stdc++.h>
#include "grader.h"
#define ff first
#define ss second
using namespace std;
vector<int> v[1009],u,m;
void dfs(int x,int p){
u.push_back(x);
for(int i:v[x]){
if(i!=p) dfs(i,x);
}
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
u={0};
int i;
for(i=1;i<=N;i++) v[i].clear();
for(i=0;i<N-1;i++){
int x=bridges[i].ff;
int y=bridges[i].ss;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,-1);
int mid,l=1,r=N;
while(r>l){
mid=(r+l)/2;
m.clear();
for(i=1;i<=mid;i++) m.push_back(u[i]);
if(query(m)) r=mid;
else l=mid+1;
}
return u[r];
}
