#include <bits/stdc++.h>
using namespace std;
#include "grader.h"
typedef pair<int, int> pii;
int I, ord[1005];
vector<int> edg[1005];
void DFS(int nod, int fth)
{
ord[++I] = nod;
for(auto nxt: edg[nod])
{
if(nxt == fth) continue;
DFS(nxt, nod);
}
}
int myQuery(int pos)
{
vector<int> v;
for(int i = 1; i <= pos; i++)
v.push_back(ord[i]);
return query(v);
}
int findEgg(int N, vector<pii> edges)
{
for(int i = 1; i <= N; i++) edg[i].clear();
for(auto e: edges)
{
edg[e.first].push_back(e.second);
edg[e.second].push_back(e.first);
}
I = 0;
DFS(1, 0);
int st = 1, dr = N;
while(st < dr)
{
int mij = st + (dr - st) / 2;
if( myQuery(mij) )
dr = mij;
else
st = mij + 1;
}
return ord[st];
}
