#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector <int> edge[10040];
int tour[10040];
int rev[10040];
//int query(vector < int > islands);
int cnt = 1;
void dfs(int id,int pa = -1){
rev[cnt] = id;
tour[id] = cnt++;
//cout << id << "\n";
for (auto ii : edge[id]){
if(ii == pa)continue;
dfs(ii,id);
}
}
bool ask(int til){
vector <int> smth;
for (int i=1; i<=til; i++){
smth.push_back(rev[i]);
}
return query(smth);
}
int findEgg(int N, vector<pair<int, int>> bridges){
memset(tour,0,sizeof(tour));
memset(rev,0,sizeof(rev));
for (auto [ft,sd] : bridges){
edge[ft].push_back(sd);
edge[sd].push_back(ft);
}
//ans.push_back(1);
cnt = 1;
dfs(1);
/*
for (int i=1; i<=N; i++){
cout << tour[i] << " " ;
}cout << "\n";
*/
/*
for (int i=1; i<=N; i++){
cout << rev[i] << " " ;
}
*/
int l=1,r=N;
while(l<r){
int mid = (l+r)/2;
if(ask(mid)){
r = mid;
}else{
l = mid+1;
}
}
for (int i=1; i<=N; i++)edge[i].clear();
return rev[l];
}
/*
int main(){
int n,m;
cin >> n >> m;
vector <pair<int,int>> brid;
for (int i=1; i<=m; i++){
int ai,bi;
cin >> ai >> bi;
brid.push_back({ai,bi});
}
findEgg(n, brid);
}
*/
