#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>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);
}
}
void go(ll u, ll p, ll lm, vector<int> &vv){
if(tin[u] > lm) return ;
vv.pb(u);
for(ll &v : g[u]){
if(v == p) continue;
go(v, u, lm, vv);
}
}
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);
int l = 1, r = n;
// for(ll i = 1; i <= n; i++) cout << tin[i] << 't';
// cout << endl;
while(l < r){
int mid = (l + r) / 2;
//cout << mid << " : " << l << ' ' << r << endl;
vector<int>v;
go(1, 0, mid, v);
if(query(v)){
r = mid;
//cout << " there is ";
}
else {
l = mid + 1;
//cout << " no no ";
}
}
return rtin[l];
}
