#include <iostream>
#include <vector>
#include "grader.h"
using namespace std;
const int M = 550;
vector<int> nei[M], vc;
int ch[M], Block[M], Lst[M], seen[M], cur;
void dfs0(int u, int p){
ch[u] = 1;
for (int i : nei[u]){
if (i == p or Block[i])
continue;
dfs0(i, u);
ch[u] += ch[i];
}
}
void Add(int u, int p){
for (int i : nei[u]){
if (i == p or Block[i])
continue;
Add(i, u);
}
vc.push_back(u);
}
int findCent(int u, int p, int rtSz){
for (int i : nei[u]){
if (i != p and !Block[i] and ch[i] * 2 > rtSz)
return findCent(i, u, rtSz);
}
return u;
}
int dfs(int u){
cur++;
dfs0(u, u);
if (ch[u] == 1)
return u;
if (ch[u] == 2){
for (int i : nei[u]){
if (Block[i])
continue;
if (query({u}))
return u;
return i;
}
}
int c = findCent(u, u, ch[u]);
dfs0(c, c);
for (int i=1;i<=ch[c];i++)
Lst[i] = -1;
for (int i : nei[c]){
if (Block[i])
continue;
for (int j=ch[c];j>=ch[i];j--){
if (Lst[j] == -1 and Lst[j - ch[i]] != -1)
Lst[j] = i;
}
}
vector<int> cld, ncld;
vc = {c};
for (int i=ch[c]-1;i>=0;i--){
if (Lst[i] != -1 and i * 2 < ch[c]){
while (i != 0)
cld.push_back(Lst[i]), seen[Lst[i]] = cur, i -= ch[Lst[i]];
}
}
for (int i : nei[u]){
if (!Block[i] and seen[i] != cur)
ncld.push_back(i);
}
for (int i : cld)
Add(i, c);
int ans = query(vc);
if (ans == 1){
for (int i : ncld)
Block[i] = 1;
return dfs(c);
}
else{
for (int i : cld)
Block[i] = 1;
if (ncld.size() == 1)
Block[c] = 1, c = ncld[0];
return dfs(c);
}
}
int findEgg(int n, vector<pair<int, int>> vec){
for (int i=1;i<=n;i++)
Block[i] = 0;
if (nei[1].size() == 0){
for (int i=0;i<vec.size();i++){
nei[vec[i].first].push_back(vec[i].second);
nei[vec[i].second].push_back(vec[i].first);
}
}
return dfs(1);
}
