#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int findEgg(int N, vector<pair<int,int>> bridges){
vector<int> adj[N];
vector<int> tin(N),seq(N);
int t = 0;
function<void(int,int)> dfs = [&](int v,int par){
seq[t] = v;
tin[v] = t++;
for(auto u:adj[v]){
if(u != par)
dfs(u,v);
}
};
for(int i = 0;i<N-1;++i){
bridges[i].first--,bridges[i].second--;
adj[bridges[i].first].push_back(bridges[i].second);
adj[bridges[i].second].push_back(bridges[i].first);
}
dfs(0,-1);
int l = 0,r = N-1;
while(l < r){
int m = (l + r)/2;
vector<int> v;
for(int i = 0;i<=m;i++){
v.push_back(seq[i] + 1);
}
if(query(v)){
r = m;
}
else l = m + 1;
}
return seq[l] + 1;
}
