#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
bool visited[1100];
vector<int> adjlst[1100];
vector<int> quer;
set<int> notdone;
int goal;
bool marked[1100];
void dfs(int i){
if(visited[i]) return;
if(goal == 0) return;
visited[i] = true;
goal--;
quer.push_back(i);
for(int j : adjlst[i]){
marked[j] = true;
dfs(j);
}
}
int findEgg (int N, vector <pair<int,int>> bridges){
set<int> notdone;
for(int i = 1; i <= N; i++){
visited[i] = false;
adjlst[i].clear();
marked[i] = false;
notdone.insert(i);
}
quer.clear();
for(int i = 0; i < N - 1; i++){
adjlst[bridges[i].first].push_back(bridges[i].second);
adjlst[bridges[i].second].push_back(bridges[i].first);
}
marked[1] = true;
while(notdone.size() != 1){
int sise = notdone.size();
goal = sise/2;
for(auto i : notdone){
if(marked[i]){
dfs(i);
}
}
/*printf("q: ");
for(auto i : quer){
printf("%d ",i);
}
printf("\n");*/
int con = quer.size();
if(query(quer)){
notdone.clear();
for(int i = quer.size() - 1; i > con - 1 - sise/2; i--){
//printf("%d ",quer[i]);
notdone.insert(quer[i]);
visited[quer[i]] = false;
quer.pop_back();
}
}
else{
for(int i = quer.size() - 1; i > con - 1 - sise/2; i--){
notdone.erase(quer[i]);
quer.pop_back();
}
}
/*for(auto i : notdone){
printf("%d ",i);
}
printf("\n");
*/
//return 1;
}
return (*notdone.begin());
}
