#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<int> ts,pmo[1024]; //path, e
int used[1024];
int n;
bool check(int x)
{
vector<int> p;
for(int i=0; i<=x; i++)
{
p.push_back(ts[i]);
}
return query(p);
}
int dnc()
{
int l=0,r=n-1;
while(l<r)
{
int mid=(l+r)/2;
if(check(mid))
{
r=mid;
}
else
l=mid+1;
}
return l;
}
void DFS(int beg)
{
used[beg]=1;
ts.push_back(beg);
for(int i=0; i<pmo[beg].size();i++)
{
int nb=pmo[beg][i];
if(!used[nb])DFS(nb);
}
}
int findEgg (int N, vector < pair < int, int > > b)
{
n=N;
memset(used,0,1024);
ts.clear();
for(int i=0; i<1024; i++)
{
pmo[i].clear();
}
for(int i=0;i<b.size();i++)
{
pmo[b[i].first].push_back(b[i].second);
pmo[b[i].second].push_back(b[i].first);
}
DFS(1);
//reverse(ts.begin(), ts.end());
return ts[dnc()];
}
