#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int findEgg (int N, vector < pair < int, int > > bridges)
{
vector<vector<int>> al(N+1);
assert((int)bridges.size()==N-1);
for(int i=0;i<N-1;i++){
al[bridges[i].first].push_back(bridges[i].second);
al[bridges[i].second].push_back(bridges[i].first);
}
vector<int> ord;
auto dfs=[&](auto dfs, int x, int p)->void{
ord.push_back(x);
for(auto it:al[x]){
if(it==p)continue;
dfs(dfs, it, x);
}
};
dfs(dfs, 1, 0);
int l=-1, r=N-1, m;
while(l < r-1){
m=(l+r)/2;
vector<int> qry(ord.begin(), ord.begin()+m+1);
if(query(qry)){
r=m;
}
else {
l=m;
}
}
return ord[r];
}
