#include <vector>
#include <iostream>
#include "grader.h"
using namespace std;
const int MAXN = 512;
vector<int> g[MAXN + 1], toquery;
vector<vector<int>> subtrees;
int viz[MAXN + 1], sz[MAXN + 1], answer;
void dfsSize(int node, int parent) {
sz[node] = 1;
for(int son : g[node]) {
if(!viz[son] && son != parent) {
dfsSize(son, node);
sz[node] += sz[son];
}
}
}
int findCentroid(int node, int limit) {
for(int son : g[node]) {
if(!viz[son] && sz[son] < sz[node] && sz[son] > limit) {
return findCentroid(son, limit);
}
}
return node;
}
void dfs(int node, int parent) {
subtrees.back().push_back(node);
for(int son : g[node]) {
if(!viz[son] && son != parent) {
dfs(son, node);
}
}
}
void decompose(int node) {
dfsSize(node, 0);
node = findCentroid(node, sz[node] / 2);
subtrees = {{node}};
for(int son : g[node]) {
if(!viz[son]) {
subtrees.push_back({});
dfs(son, node);
}
}
int st = 0, dr = (int)subtrees.size() - 1, poz = 0;
while(st <= dr) {
int mij = (st + dr) / 2;
toquery.clear();
for(int i = 0; i <= mij; i++) {
for(int node : subtrees[i]) {
toquery.push_back(node);
}
}
if(query(toquery)) {
poz = mij;
dr = mij - 1;
} else {
st = mij + 1;
}
}
if(poz == 0) {
answer = node;
return;
}
viz[node] = 1;
int cnt = 0;
for(int son : g[node]) {
if(!viz[son]) {
cnt++;
if(cnt == poz) {
decompose(son);
return;
}
}
}
}
int findEgg(int n, vector<pair<int, int>> edges) {
for(int i = 1; i <= n; i++) {
g[i].clear();
viz[i] = 0;
}
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);
}
decompose(1);
return answer;
}
