#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int findEgg (int N, vector < pair < int, int > > bridges)
{
//if (query ({1})) return 1;
int a, b;
std::set<int> con[N+3];
std::set<int> set;
int arr[N+3] = {};
for(auto x : bridges){
a = x.first;
b = x.second;
set.insert(a);
set.insert(b);
con[a].insert(b);
con[b].insert(a);
}
std::vector<int> test;
std::vector<int> cat;
int round = 1;
int senders = 0;
int total = (N+1)/2;
int ans;
a = 1;
while(true){
test.clear();
cat.clear();
std::queue<int> que;
senders = 0;
total = (set.size()+1)/2;
int a = bridges[0].first;
que.push(a);
arr[a] = round;
test.push_back(a);
if(set.find(a)!=set.end()){
cat.push_back(a);
++senders;
}
while(!que.empty()){
a = que.front();
que.pop();
if(senders==total){
break;
}
//printf("%d*\n", a);
for(int x : con[a]){
if(arr[x]!=round){
que.push(x);
arr[x] = round;
test.push_back(x);
if(set.find(x)!=set.end()){
cat.push_back(x);
++senders;
if(senders==total){
break;
}
}
}
}
}
ans = query(test);
if(ans){
set.clear();
for(int x: cat){
set.insert(x);
}
}
else{
for(int x: test){
set.erase(x);
}
}
/*
for(int x : set){
printf("%d ", x);
}
printf("\n");
//*/
if(set.size()==1){
return *set.begin();
}
++round;
}
return 0;
}
