#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define dim 514
vector<int> v[dim],a;
void dfs(int nod,int tata)
{
a.push_back(nod);
for(auto y:v[nod])
{
if(y!=tata)
{
dfs(y,nod);
}
}
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
int i,st,dr,mijl,maxi;
for(i=1;i<=N;i++)
{
v[i].clear();
}
for(auto muchie : bridges)
{
v[muchie.first].push_back(muchie.second);
v[muchie.second].push_back(muchie.first);
}
a.clear();
dfs(1,0);
st=0;dr=N-1;
maxi=-1;
while(st<dr)
{
mijl=(st+dr+1)/2;
vector<int> q;
for(i=0;i<mijl;i++)
q.push_back(a[i]);
if(query(q))
{
dr=mijl-1;
}
else
{
if(mijl>maxi)
maxi=mijl;
st=mijl;
}
}
return a[st];
}
