#include <bits/stdc++.h> using namespace std; int query(vector<int> islands); static const int MAXN = 520; vector<int> adj[MAXN]; bool removed[MAXN]; int subSize[MAXN]; int N; // Computer sub-tree sizes void dfsSize(int u, int p) { subSize[u] = 1; for (int v : adj[u]) { if (v == p || removed[v]) continue; dfsSize(v, u); subSize[u] += subSize[v]; } } // Find Centroid int dfsCentroid(int u, int p, int total) { for (int v : adj[u]) { if (v == p || removed[v]) continue; if (subSize[v] > total / 2) return dfsCentroid(v, u, total); } return u; } int getCentroid(int root) { dfsSize(root, -1); return dfsCentroid(root, -1, subSize[root]); } // Collect all nodes in a component void collect(int u, int p, vector<int>& comp) { comp.push_back(u); for (int v : adj[u]) { if (v == p || removed[v]) continue; collect(v, u, comp); } } // Recursive solve function int solve(int root) { int c = getCentroid(root); // If there is only 1 node left dfsSize(c, -1); if (subSize[c] == 1) return c; removed[c] = true; for (int v : adj[c]) { if (removed[v]) continue; vector<int> component; collect(v, c, component); // Make query set: centroid + component vector<int> ask = component; ask.push_back(c); if (query(ask)) { return solve(v); } } // If egg is not in any component, it must be the centroid return c; } int findEgg(int n, vector<pair<int,int>> bridges) { N = n; for (int i = 1; i <= N; i++) { adj[i].clear(); removed[i] = false; } for (auto &e : bridges) { adj[e.first].push_back(e.second); adj[e.second].push_back(e.first); } return solve(1); }