#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> a;
vector<int> v[513];
int viz[513];
vector<int> aux;
void dfs(int nod){
int i;
viz[nod]=1;
a.push_back(nod);
for(i=0;i<v[nod].size();i++){
if(viz[v[nod][i]]==0) dfs(v[nod][i]);
}
}
int findEgg(int n,vector<pair<int,int>> bridges){
a.clear();aux.clear();
int st,dr,rasp,mij,i;
for(i=0;i<=512;i++){
v[i].clear();viz[i]=0;
}
for(i=0;i<bridges.size();i++){
v[bridges[i].first].push_back(bridges[i].second);
v[bridges[i].second].push_back(bridges[i].first);
}
dfs(1);
st=0;dr=a.size()-1;
while(st<=dr){
mij=(st+dr)/2;aux.clear();
if(mij>=a.size()) return {0};
for(i=0;i<=mij;i++){
aux.push_back(a[i]);
}
if(query(aux)){
rasp=mij;dr=mij-1;
}else st=mij+1;
}
return rasp;
}
