#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) {
adj.clear();
subtree.clear();
adj.assign(N + 1, vector<int>());
for (auto& edge : bridges) {
adj[edge.first].push_back(edge.second);
adj[edge.second].push_back(edge.first);
}
int current = 1;
int parent = -1;
while (true) {
bool foundInChild = false;
for (int neighbor : adj[current]) {
if (neighbor == parent) continue;
subtree.clear();
dfs(neighbor, current);
if (query(subtree) == 1) {
parent = current;
current = neighbor;
foundInChild = true;
break;
}
}
if (!foundInChild) {
return current;
}
}
}
