#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int dfs(int cn, map<int,int>&preorder, map<int, vector<int>>&adjlist, int curr, vector<int>&corrfrom)
{
preorder[cn]=++curr;
corrfrom[preorder[cn]]=cn;
for(int to:adjlist[cn])
{
if(preorder.count(to))continue;
curr=dfs(to,preorder,adjlist,curr,corrfrom);
}
return curr;
}
int findEgg (int N, vector<pair<int,int>>bridges)
{
map<int,int>preorder;map<int,vector<int>>adjlist;
vector<int>corrfrom(N+1);
for(int a=0;a<(N-1);a++)
{
int t1=bridges[a].first,t2=bridges[a].second;
adjlist[t1].push_back(t2);
adjlist[t2].push_back(t1);
}
dfs(1,preorder,adjlist,0,corrfrom);
int hi=N,lo=0,mid;
while(hi>lo+1)
{
mid=(hi+lo)/2;
vector<int>queset;
for(int a=lo+1;a<=mid;a++){queset.push_back(corrfrom[a]);}
if(query(queset))
{
hi=mid;
}
else
{
lo=mid;
}
}
return corrfrom[hi];
}
