#include <vector>
#include <iostream>
#include "grader.h"
using namespace std;
const int MAXN = 512;
vector<int> g[MAXN + 1], v;
int ord[MAXN + 1], ptr;
void dfs(int node, int parent) {
ord[++ptr] = node;
for(int son : g[node]) {
if(son != parent) {
dfs(son, node);
}
}
}
int findEgg(int n, vector<pair<int, int>> edges) {
for(int i = 1; i <= n; i++) {
g[i].clear();
}
for(int i = 0; i < n - 1; i++) {
g[edges[i].first].push_back(edges[i].second);
g[edges[i].second].push_back(edges[i].first);
}
ptr = 0;
dfs(1, 0);
int st = 1, dr = n, answer = 1;
while(st <= dr) {
int mij = (st + dr) / 2;
v.clear();
for(int i = 1; i <= mij; i++) {
v.push_back(ord[i]);
}
if(query(v)) {
answer = mij;
dr = mij - 1;
} else {
st = mij + 1;
}
}
return ord[answer];
}
