#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<vector<int>> adj;
vector<int> ordre;
void dfs(int actual, int anterior){
ordre.push_back(actual);
for (auto v : adj[actual]){
if (v != anterior){
dfs(v, actual);
}
}
}
int findEgg (int N, vector<pair<int, int>> bridges){
adj.resize(N+1);
for(int i = 0; i < N-1; i++){
adj[bridges[i].first].push_back(bridges[i].second);
adj[bridges[i].second].push_back(bridges[i].first);
}
dfs(1, 0);
int r = N-1, l = 1;
vector<int> islands;
while (r >= l){
int m = (r+l)/2;
islands.resize(m);
for (int i = 0; i < m; i++){
islands[i] = ordre[i];
}
if (query(islands)){
r = m-1;
}
else{
l = m+1;
}
}
return ordre[r];
}
