#include <bits/stdc++.h>
#include "grader.h"
#define pb(x) push_back(x)
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define MAXN 512
using namespace std;
vector<int>adj[MAXN],v;
void dfs(int nd,int pr){
v.pb(nd);
tr(it,adj[nd])
if(*it!=pr)
dfs(*it,nd);
}
int findEgg (int N, vector < pair < int, int > > bridges){
for(int i=0;i<N;i++)adj[i].clear();
v.clear();
for(int i=0;i<N-1;i++){
int u=bridges[i].first-1;
int v=bridges[i].second-1;
adj[u].pb(v);adj[v].pb(u);
}
dfs(0,-1);
int st=0,en=N-1;
while(st<en){
int mid=(st+en)>>1;
vector<int>cur;
for(int i=0;i<=mid;i++)cur.pb(v[i]+1);
if(query(cur))en=mid;
else st=mid+1;
}
return v[st]+1;
}
