#include <bits/stdc++.h>
#include "grader.h"
#define DEBUG 0
using namespace std;
const int MAX = 520;
int timer;
vector <int> adj[MAX];
int st[MAX];
void dfs(int u, int p) {
st[++timer] = u;
for(auto v : adj[u]) {
if(v != p) {
dfs(v, u);
}
}
}
int findEgg(int N, vector <pair <int, int>> bridges) {
timer = 0;
for(int i = 1; i <= N; i++) {
adj[i].clear();
}
for(auto [u, v] : bridges) {
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, -1);
int l = 1, r = N;
while(l < r) {
int mid = (l + r) / 2;
vector <int> islands;
for(int i = 1; i <= mid; i++) {
islands.push_back(st[i]);
}
if(query(islands) == 1) {
r = mid;
}
else {
l = mid + 1;
}
}
return st[l];
}
