#include <iostream>
#include "grader.h"
#include <vector>
using namespace std;
vector<int> v[515],t;
void dfs(int node,int p)
{
t.push_back(node);
for (int u:v[node])
{
if (u!=p)
dfs(u,node);
}
}
bool check(int m)
{
vector<int> tmp;
for (int i=0;i<=m;i++)
tmp.push_back(t[i]);
return query(tmp);
}
int findEgg(int n,vector<pair<int,int> > e)
{
if (t.empty())
{
for (auto p:e)
{
v[p.first].push_back(p.second);
v[p.second].push_back(p.first);
}
dfs(1,0);
}
int st=0,en=n-1;
while (st!=en)
{
int mid=(st+en)/2;
if (check(mid))
en=mid;
else
st=mid+1;
}
return t[st];
}
