#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);
}
