#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<int> vis;
vector<int> ord = {0};
vector<vector<int>> adjlist;
void dfs(int u,int p ){
for(auto x : adjlist[u]){
if (x == p){
continue;
}
ord.push_back(x);
dfs(x,u);
}
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
vis.assign(N, 0); // or fill(vis.begin(), vis.end(), 0);
adjlist.assign(N, {});
ord.clear();
ord.push_back(0); // if you want to re-init
for(int i = 0;i<N-1;i++){
int a = bridges[i].first;
int b = bridges[i].second;
a--;b--;
adjlist[a].push_back(b);
adjlist[b].push_back(a);
}
dfs(0,-1);
long long lb = 0;
long long ub = N-1;
long long mid = -1;
long long ans = -1;
while (lb < ub){
mid = (lb + ub) / 2;
vector<int> temp;
for(int i = 0;i<=mid;i++){
temp.push_back(ord[i] + 1);
}
int r = query(temp);
if (r == 0){
lb = mid + 1;
}
else{
ub = mid;
}
}
return ord[lb] + 1;
}
