#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int findEgg(int n, vector<pair<int, int>>bridges){
// vector 1D de todas las islas
vector<vector<int>> lst(n,vector<int>());
for(auto b:bridges){
lst[b.first-1].push_back(b.second-1);
lst[b.second-1].push_back(b.first-1);
}
vector<int> islands;
int isl=0;
while((int) lst[isl].size()!=1) isl++; // busco un extremo
islands.push_back(isl);
int l_isl = isl;
isl = lst[l_isl][0];
islands.push_back(isl);
while((int) islands.size() != n){
int t = isl;
if(lst[isl][0]==l_isl) isl = lst[isl][1];
else isl = lst[isl][0];
l_isl = t;
islands.push_back(isl);
}
// binary search
int l = 0;
int r = n-1;
while(l<=r){
int m = (l+r)/2;
bool egg = query({islands.begin()+l,islands.begin()+l+m});
if(egg) r = m-1;
else l = m+1;
}
return l;
}
