#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<int> order, g[1010];
void dfs(int no, int pa) {
order.push_back(no);
for(auto i: g[no]) {
if(i == pa) continue;
dfs(i, no);
}
}
int findEgg(int N, vector<pair<int, int>> bridges) {
for(int i=1; i<=N; i++) {
g[i].clear();
}
order.clear();
for(auto i: bridges) {
g[i.first].push_back(i.second);
g[i.second].push_back(i.first);
}
dfs(1, -1);
int l=1, r=N;
while(l < r) {
int mid = (l+r)/2;
vector<int> v;
for(int i=0; i<mid; i++) {
v.push_back(order[i]);
}
if(query(v)) {
r = mid;
} else {
l = mid+1;
}
}
return order[l-1];
}
