#include<bits/stdc++.h>
#include "grader.h"
using namespace std;
int findEgg (int N, vector<pair<int,int>>bridges)
{
vector<int>v[N+1];
for(int i=0; i<N-1; i++){
int fi=bridges[i].first;
int se=bridges[i].second;
v[fi].push_back(se);
v[se].push_back(fi);
}
queue<int>q;
q.push(1);
int L[N+1];
fill(L,L+N+1,0);
L[1]=1;
vector<int>va;
while(q.size()){
int k=q.front();
q.pop();
va.push_back(k);
//l[k]=1;
for(auto a:v[k]){
if(L[a]==0){
L[a]=1;
q.push(a);
}
}
}
int l=0,r=N-2;
int ans=-1;
while(l<=r){
int m=(l+r)/2;
vector<int>bati;
for(int i=l; i<m; i++){
bati.push_back(va[i]);
}
if(query(bati)==1){
r=m-1;
ans=m;
}
else{
l=m+1;
}
}
if(ans==-1){
//cout<<va[N-1]<<endl;
int k=va[N-1];
return k;
}
return ans;
}
