#include "grader.h"
#include <iostream>
#include <vector>
using namespace std;
void dfs_function(int N, vector<vector<int>>&listaAdy, vector<int>&dfs, int i, int padre){
dfs.push_back(i);
for (int conexiones: listaAdy[i]){
if (conexiones!=padre) dfs_function(N, listaAdy, dfs, conexiones, i);
}return;
}
int findEgg(int N, vector<pair<int,int>>bridges){
vector<int>islands;
vector<vector<int>>listaAdy(N);
for (int i=0; i<N-1; i++){
int a=bridges[i].first-1;
int b=bridges[i].second-1;
listaAdy[a].push_back(b);
listaAdy[b].push_back(a);
}vector<int>dfs;
dfs_function(N, listaAdy, dfs, 0, -1);
int l=0, r=N-1, m;
while (l<r){
m=(r-l)/2+l;
islands.clear();
for (int i=0; i<=m; i++) islands.push_back(dfs[i]+1);
if (query(islands)==1) r=m;
else l=m+1;
}return dfs[l]+1;
}
