#include <bits/stdc++.h>
#include "grader.h"
//#include "grader.cpp"
using namespace std;
int findEgg (int n, vector < pair < int, int > > bridges){
vector<vector<int>> g(n + 5);
for(auto [a, b] : bridges) {
g[a].push_back(b);
g[b].push_back(a);
};
vector<int> tin(n + 5, 0);
int tim = 1;
auto dfs = [&](auto dfs, int ps, int pr) -> void{
tin[ps] = tim++;
for(int to : g[ps])
if(to != pr)
dfs(dfs, to, ps);
};
dfs(dfs, 1, 1);
//for(int i = 1; i <= n; i ++ ){
//cout << i << ' ' << tin[i] << '\n';
//}
int ans = 1;
int l = 1, r = n;
while(l < r){
int m = (l+r)>>1;
//cout << l << ' ' << r << ' ' << m << '\n';
vector<int> lf;
for(int i = 1; i <= n; i++)
if(l <= tin[i] && tin[i] <= m)
lf.push_back(i);
if(query(lf)){
ans = m;
r = m;
}else{
ans = m+1;
l = m + 1;
}
};
for(int i = 1; i <= n; i++){
if(tin[i] == ans){
ans = i;
break;
}
}
return ans;
}
