#include <iostream>
#include <vector>
#include "grader.h"
using namespace std;
const int M = 550;
vector<int> nei[M], ord;
void dfs(int u, int p){
ord.push_back(u);
for (int i : nei[u]){
if (i == p)
continue;
dfs(i, u);
}
}
int ask(int len){
vector<int> vc;
for (int i=0;i<=len;i++)
vc.push_back(ord[i]);
return query(vc);
}
int findEgg(int n, vector<pair<int, int>> vec){
for (int i=0;i<vec.size();i++){
if (ord.size() > 0) continue;
nei[vec[i].first].push_back(vec[i].second);
nei[vec[i].second].push_back(vec[i].first);
}
dfs(1, 0);
int l = -1, r = n-1;
while (l + 1 < r){
int mid = (l + r) / 2;
if (ask(mid))
r = mid;
else
l = mid;
}
return ord[r];
}
