#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); 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(); } } bool st = query(vals); if(st){ for(int u : pit) del[u] = 1; } else{ for(int u : vit) del[u] = 1; } 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); }