#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<int> adj[2005];
vector<int> bruhs;
void dfs(int x, int p = -1) {
bruhs.push_back(x);
for(auto &e:adj[x]) {
if(e == p) continue;
dfs(e, x);
}
}
int findEgg (int N, vector < pair < int, int > > bridges) {
for(int i=0;i<=N;i++) adj[i].clear();
bruhs.clear();
for(auto &e:bridges) {adj[e.first].push_back(e.second); adj[e.second].push_back(e.first);}
dfs(1);
int l = 0, r = N-1, mid;
while(l < r) {
mid = (l+r) >> 1;
vector<int> toask;
for(int i=0;i<=mid;i++) toask.push_back(bruhs[i]);
if(query(toask)) r = mid;
else l = mid+1;
}
return bruhs[l];
}
