#include <vector> using namespace std; int query(vector<int> islands); vector<vector<int>> adj; vector<int> subtree; vector<int> subtree_size; vector<bool> removed; void calc_size(int node, int parent) { subtree_size[node] = 1; for (int next : adj[node]) { if (next != parent && !removed[next]) { calc_size(next, node); subtree_size[node] += subtree_size[next]; } } } int find_centroid(int node, int parent, int tree_size) { for (int next : adj[node]) { if (next != parent && !removed[next] && subtree_size[next] > tree_size / 2) { return find_centroid(next, node, tree_size); } } return node; } void get_subtree(int node, int parent) { subtree.push_back(node); for (int next : adj[node]) { if (next != parent && !removed[next]) { get_subtree(next, node); } } } int solve(int node) { calc_size(node, -1); int centroid = find_centroid(node, -1, subtree_size[node]); // Check each subtree of the centroid for (int child : adj[centroid]) { if (removed[child]) continue; subtree.clear(); get_subtree(child, centroid); if (query(subtree) == 1) { // Egg is in this subtree return solve(child); } } // Egg is at centroid return centroid; } int findEgg(int N, vector<pair<int, int>> bridges) { // Build adjacency list adj.assign(N + 1, vector<int>()); subtree_size.assign(N + 1, 0); removed.assign(N + 1, false); for (auto& edge : bridges) { adj[edge.first].push_back(edge.second); adj[edge.second].push_back(edge.first); } return solve(1); }