#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> graph[513];
vector<int> all;
void dfs(int x, int p){
all.push_back(x);
for (auto u : graph[x]){
if (u == p) continue;
else dfs(u,x);
}
}
int findEgg(int N, vector < pair < int, int > > bridges){
for (int i = 1; i<=N; i++){
graph[i].clear();
}
all.clear();
for (auto u : bridges){
graph[u.first].push_back(u.second);
graph[u.second].push_back(u.first);
}
dfs(1,0);
int lo = 0;
int hi = N-1;
int mid;
while (lo < hi){
mid = (lo+hi)/2;
if (query(vector<int>(all.begin(),all.begin()+mid+1))){
//it works
hi = mid - 1;
}
else{
lo = mid + 1;
}
}
return all[lo];
}
