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