#include <vector>
#include <queue>
#include "grader.h"
#define endl '\n'
#define ll long long
using namespace std;
int n;
int used[1024];
vector <int> vo[1024];
vector <int> v[1024];
vector <int> vd[1024];
void reset()
{
for(int i=1;i<514;i++)
used[i]=0;
}
void bfs()
{
reset();
queue<int> q;
q.push(1);
used[1]=1;
while(!q.empty())
{
int c=q.front();
q.pop();
for(int i=0;i<vo[c].size();i++)
{
int nb=vo[c][i];
if(!used[nb])
{
used[nb]=1;
v[c].push_back(nb);
q.push(nb);
}
}
}
}
vector<int> c;
void dfs(int beg)
{
used[beg]=1;
for(int i=0;i<c.size();i++)
{
vd[c[i]].push_back(beg);
}
c.push_back(beg);
for(int i=0;i<v[beg].size();i++)
{
int nb=v[beg][i];
if(!used[nb])
{
dfs(nb);
}
}
c.pop_back();
}
int dnc(int beg)
{
while(vd[beg].size()>1)
{
for(int i=0;i<v[beg].size();i++)
{
int nb=v[beg][i];
//for(int j=0;j<vd[nb].size();j++)cout<<vd[nb][j]<<" ";
//cout<<endl;
if(query(vd[nb])==1)
{
beg=nb;
break;
continue;
}
}
return beg;
}
return beg;
}
int findEgg (int N, vector < pair < int, int > > b)
{
n=N;
for(int i=1;i<=512;i++)
{
vo[i].clear();
v[i].clear();
vd[i].clear();
vd[i].push_back(i);
}
reset();
for(int i=0;i<b.size();i++)
{
vo[b[i].first].push_back(b[i].second);
vo[b[i].second].push_back(b[i].first);
}
bfs();
reset();
dfs(1);
return dnc(1);
}
