#include <bits/stdc++.h>
#include "grader.h"
#define ll long long
#define pb push_back
using namespace std;
ll timer = 0;
vector<vector<ll>>g;
vector<ll>ch, tin, rtin;
void dfs(ll u, ll p = -1){
tin[u] = ++timer;
rtin[timer] = u;
for(ll &v : g[u]){
if(v == p) continue;
dfs(v, u);
}
}
int findEgg (int n, vector < pair < int, int > > bridges){
g.assign(n + 1, {});
tin.assign(n + 1, 0);
rtin.assign(n + 2, 0);
for(auto &[a, b] : bridges){
g[a].pb(b), g[b].pb(a);
}
timer = 0; dfs(1);
ll l = 1, r = n;
int best = 0;
while(l < r){
ll mid = (l + r) / 2;
//cout << mid << " : " << l << ' ' << r << endl;
vector<int>v;
for(ll i = l; i <= mid; i++){
v.pb(rtin[i]); //cout << rtin[i] << 'v';
}
//cout << endl;
if(query(v)) r = mid;
else l = mid + 1;
}
return rtin[l];
}
