#include <vector>
using namespace std;
int query(vector<int> islands);
vector<vector<int>> adj;
vector<int> subtree;
void dfs(int node, int parent) {
subtree.push_back(node);
for (int next : adj[node]) {
if (next != parent) {
dfs(next, node);
}
}
}
int findEgg(int N, vector<pair<int, int>> bridges) {
// Build adjacency list
adj.assign(N + 1, vector<int>());
for (auto& edge : bridges) {
adj[edge.first].push_back(edge.second);
adj[edge.second].push_back(edge.first);
}
// Start from node 1
int current = 1;
int parent = -1;
while (true) {
// Check all children subtrees of current node
bool foundInChild = false;
for (int neighbor : adj[current]) {
if (neighbor == parent) continue; // Skip parent
// Get all nodes in this child's subtree
subtree.clear();
dfs(neighbor, current);
// Query this subtree
if (query(subtree) == 1) {
// Egg is in this subtree, move to it
parent = current;
current = neighbor;
foundInChild = true;
break;
}
}
// If egg not in any child subtree, it's at current node
if (!foundInChild) {
return current;
}
}
}
