#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
const int N = 520;
int n;
vector<int> g[N];
vector<int> a;
bool vis[N];
void dfs(int i){
a.push_back(i);
vis[i] = 1;
for(auto x : g[i]){
if(!vis[x]){
dfs(x);
}
}
}
int findEgg (int nn, vector < pair < int, int > > bridges)
{
memset(vis, 0, sizeof vis);
n = nn;
for(auto b : bridges){
g[b.first].push_back(b.second);
g[b.second].push_back(b.first);
}
dfs(1);
int l = 0, r = n-1, ans = -1;
while(l <= r){
if(r == l){
ans = a[r];
break;
}
int mid = (l+r)/2;
vector<int> aux;
for(int j=0; j<=mid; ++j){
aux.push_back(a[j]);
}
if(query(aux)){
ans = a[mid];
r = mid-1;
} else {
l = mid+1;
}
}
return ans;
}
