#include <bits/stdc++.h> #include "grader.h" using namespace std; const int MAXN = (1 << 9) + 3; int p1, p2, diff; int del[MAXN], sz[MAXN]; vector < int > g[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 upd(int v, int p, int s){ for(int u : g[v]){ if(!del[u] && u != p){ upd(u, v, s); if(abs(sz[u] * 2 - s) < diff) diff = abs(sz[u] * 2 - s), p1 = v, p2 = 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 centroid(int v){ calc(v); if(sz[v] == 1) return v; diff = (1 << 10), p1 = p2 = 0; upd(v, -1, sz[v]); vector < int > v1, v2; add(p1, p2, v1); add(p2, p1, v2); if(query(v1)){ for(int x : v2) del[x] = 1; return centroid(v1.back()); } else{ for(int x : v1) del[x] = 1; return centroid(v2.back()); } } int findEgg (int n, vector < pair < int, int > > bridges){ for(int i = 1; i <= n; i++) g[i].clear(), sz[i] = del[i] = 0; for(auto [x, y] : bridges) g[x].push_back(y), g[y].push_back(x); return centroid(1); }