#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);
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;
vector<int>v;
for(ll i = 1; i <= rtin[mid]; i++)
v.pb(i);
if(query(v)){
r = mid - 1;
best = mid;
}
else l = mid + 1;
}
return best;
}
