#include "bits/stdc++.h"
#include "grader.h"
// #include "grader.cpp"
#define SZ(s) (int)s.size()
#define ss second
#define ff first
using namespace std;
vector <int> ve[513];
bool tr;
vector <int> path;
vector <pair<int,int>> v1;
void dfs(int x, int y){
path.push_back(x);
for(auto i : ve[x]){
if(i == y) continue;
dfs(i,x);
path.push_back(x);
}
}
int findEgg (int n, vector < pair < int, int > > briges) {
map <int,bool> vis;
if(!tr){
tr = true;
for(auto [i,j] : briges){
ve[i].push_back(j);
ve[j].push_back(i);
}
dfs(1,0);
vis.clear();
for(int i = 0; i < SZ(path); i++){
if(vis.find(path[i]) == vis.end()) v1.push_back({path[i],i}), vis[path[i]] = true;
}
}
int l = 0, r = SZ(v1)-1;
while(l < r){
int md = (l + r) / 2;
vis.clear();
vector <int> qwe;
for(int i = v1[l].ss; i <= v1[md].ss; i++){
if(vis.find(path[i]) == vis.end()) qwe.push_back(path[i]), vis[path[i]] = true;
}
bool qw = query(qwe);
if(qw) r = md;
else l = md+1;
}
return v1[l].ff;
}
