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