#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
const int MAXN = (1 << 9) + 3;
int del[MAXN], sz[MAXN], dp[MAXN];
vector < int > g[MAXN], part[MAXN];
void calc(int v, int p = -1){
sz[v] = 1;
for(int u : g[v])
if(u != p && !del[u])
calc(u, v), sz[v] += sz[u];
}
void add(int v, int p, vector < int > &x){
x.push_back(v);
for(int u : g[v])
if(u != p && !del[u])
add(u, v, x);
}
int find(int v, int p, int s){
for(int u : g[v])
if(u != p && !del[u] && sz[u] * 2 >= s)
return find(u, v, s);
return v;
}
int centroid(int v, int n){
calc(v);
v = find(v, -1, sz[v]);
calc(v);
if(sz[v] == 2){
if(query({v})) return v;
for(int u : g[v])
if(!del[u])
return u;
}
for(int x = 0; x <= sz[v]; x++) dp[x] = -1;
dp[0] = 0;
bool ok = 0;
for(int u : g[v])
if(!del[u])
part[sz[u]].push_back(u), ok = 1;
if(!ok) return v;
for(int u : g[v])
if(!del[u])
for(int x = sz[v] / 2; x >= sz[u]; x--)
if(dp[x - sz[u]] != -1 && dp[x] == -1)
dp[x] = x - sz[u];
int opt = 0;
for(int x = 1; x <= sz[v] / 2; x++)
if(dp[x] != -1)
opt = x;
vector < int > cur;
while(opt != 0){
cur.push_back(opt - dp[opt]);
opt = dp[opt];
}
vector < int > vals, vit, pit;
for(int x : cur){
add(part[x].back(), v, vals);
vit.push_back(part[x].back());
part[x].pop_back();
}
for(int i = 1; i <= sz[v]; i++){
while(part[i].size()){
pit.push_back(part[i].back());
part[i].pop_back();
}
}
int ch = 0;
for(int u : g[v])
if(!del[u])
ch++;
if(ch > 1) vals.push_back(v);
bool st = query(vals);
if(st){
for(int u : pit) del[u] = 1;
}
else{
for(int u : vit) del[u] = 1;
}
// cout << "centroid " << v << " --- ";
// for(int u : g[v])
// if(!del[u])
// cout << u << ' ';
// cout << '\n';
// cout << "tried on " << st << " --- ";
// for(int u : vals) cout << u << ' ';
// cout << '\n';
return centroid(v, n);
}
int findEgg (int n, vector < pair < int, int > > bridges){
for(int i = 1; i <= n; i++) g[i].clear(), part[i].clear(), sz[i] = del[i] = 0, dp[i] = -1;
for(auto [x, y] : bridges) g[x].push_back(y), g[y].push_back(x);
return centroid(1, n);
}
