#include <vector> using namespace std; int query(vector<int> islands); vector<vector<int>> adj; vector<bool> visited; vector<int> subtree; void dfs(int node, int parent) { visited[node] = true; subtree.push_back(node); for (int next : adj[node]) { if (next != parent && !visited[next]) { 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); } // Binary search approach on the tree int current = 1; while (true) { bool found = false; for (int neighbor : adj[current]) { // Get all nodes in this subtree subtree.clear(); visited.assign(N + 1, false); visited[current] = true; // Mark current as visited to avoid going back dfs(neighbor, current); // Query this subtree if (query(subtree) == 1) { current = neighbor; found = true; break; } } // If no subtree contains the egg, it must be at current node if (!found) { return current; } } }