#include <vector>
#include <queue>
#include "grader.h"
#define endl '\n'
#define ll long long
using namespace std;
int n;
int used[1024];
vector <int> v[1024];
vector <int> mno;
bool f=false;
void dfs(int beg)
{
used[beg]=1;
mno.push_back(beg);
///cout << "-------------" << endl;
///cout<<beg<<endl;
for(int i=0; i<v[beg].size(); i++)
{
int nb=v[beg][i];
///cout << nb << endl;
if(!used[nb])
{
dfs(nb);
}
}
}
int bin()
{
int l=1;
int r=n,mid;
while(l<r)
{
vector<int> x;
mid=(l+r)/2;
for(int i=0; i<mid; i++)
{
x.push_back(mno[i]);
}
if(query(x))
{
r=mid;
}
else
{
l=mid+1;
}
}
return l-1;
}
int findEgg (int N, vector < pair < int, int > > b)
{
if(!f)
{
n=N;
for(int i=0; i<b.size(); i++)
{
v[b[i].first].push_back(b[i].second);
v[b[i].second].push_back(b[i].first);
}
dfs(1);
f=1;
}
//cout<<155555<<endl;
return mno[bin()];
}
