#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<int> vis;
vector<int> ord;
vector<vector<int>> adjlist;
void dfs(int x){
vis[x] = 1;
for (auto nxt : adjlist[x])
if (!vis[nxt])
dfs(nxt);
ord.push_back(x);
}
int findEgg (int N, vector < pair < int, int > > bridges)
{ vis.resize(N);
adjlist.resize(N);
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);
reverse(ord.begin(),ord.end());
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 = lb;i<=mid;i++){
temp.push_back(ord[i] + 1);
}
int r = query(temp);
if (r == 0){
lb = mid + 1;
}
else{
ub = mid - 1;
}
}
return ord[lb] + 1;
}
