#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
template<class T> using matrix = vector<vector<T>>;
void dfs(int u, int p, vector<int>& order, matrix<int>& G){
order.push_back(u);
for(auto v : G[u]){
if(v == p) continue;
dfs(v, u, order, G);
}
}
int findEgg(int N, vector <pair<int, int>> bridges){
matrix<int> G(N + 1);
for(auto [u, v] : bridges){
G[u].push_back(v);
G[v].push_back(u);
}
vector<int> dfsorder;
dfs(1, 1, dfsorder, G);
int low = 0, high = N - 1;
while(low < high){
int mid = (low + high) / 2;
vector<int> q = dfsorder;
q.resize(mid + 1);
if(query(q)){
high = mid;
}
else{
low = mid + 1;
}
}
return dfsorder[low];
}
