#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[1005],path;
void dfs(int u,int p){
path.push_back(u);
for(auto v:adj[u]){
if(v==p) continue;
dfs(v,u);
}
}
int findEgg (int N, vector < pair < int, int > > bridges){
path.clear();
for(int i=0;i<=N;i++) adj[i].clear();
for(auto [u,v]:bridges){
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1,1);
// for(auto u:path) cout<<u <<" ";
// cout<<"\n";
int l=0,r=N-1;
while(l<r){
int mid=(l+r)/2;
vector<int> tmp;
for(int i=0;i<=mid;i++) tmp.push_back(path[i]);
if(query(tmp)) r=mid;
else l=mid+1;
}
return path[l];
}
