#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define st first
#define nd second
using ll = long long;
using ld = long double;
const int MN = 1000;
vector <int> v[MN];
bool visited[MN];
vector <int> ord;
void dfs(int x) {
visited[x] = 1;
ord.pb(x);
for(int i : v[x]) {
if(!visited[i]) {
dfs(i);
}
}
}
int findEgg(int N, vector < pair < int, int > > bridges) {
for(int i = 0; i < N; i++) {
visited[i] = 0;
v[i].clear();
}
ord.clear();
for(auto i : bridges) {
v[i.st].pb(i.nd);
v[i.nd].pb(i.st);
}
dfs(1);
int l = 1, r = N, s = 0;
while(l < r) {
s = (l + r) / 2;
vector <int> ss = {};
for(int i = 0; i < s; i++) {
ss.pb(ord[i]);
}
if(query(ss) == 0) {
l = s + 1;
}
else {
r = s;
}
}
return ord[l - 1];
}
