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