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