#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<vector<int>> g;
vector<int> o;
void dfs(int curr,int pre){
o.emplace_back(curr);
for(auto x : g[curr]){
if(x == pre) continue;
dfs(x,curr);
}
}
int findEgg(int N, vector<pair<int, int>> bridges)
{
o.clear();
g.clear();
g.resize(N + 1);
for(auto x : bridges){
g[x.first].emplace_back(x.second);
g[x.second].emplace_back(x.first);
}
dfs(1,0);
int l = 0, r = N - 1,ans = o[0];
while(l < r){
int mid = (r - l) / 2 + l;
vector<int> ask;
for(int i = 0; i <= mid; i++){
ask.emplace_back(o[i]);
}
if(query(ask)){
ans = o[mid];
r = mid - 1;
}
else{
l = mid + 1;
}
}
return ans;
}
