#include <iostream> #include <algorithm> #include <vector> const int MAXN = 512 + 1; int n; std::vector<int> tree[MAXN]; std::vector<int> order; void dfs(int node, int par) { order.push_back(node); for(int to : tree[node]) { if(to == par) continue; dfs(to, node); } } int query(std::vector<int> islands); bool f(int idx) { std::vector<int> prefix; for(int i = 0 ; i < idx ; ++i) { prefix.push_back(order[i]); } return query(prefix); } int findEgg(int N, std::vector<std::pair<int,int>> bridges) { n = N; for(auto &[a, b] : bridges) { tree[a].push_back(b); tree[b].push_back(a); } dfs(1, -1); int l = -1, r = n + 1; while(l + 1 < r) { int mid = (l + r) / 2; if(!f(mid)) l = mid; else r = mid; } return order[l + 1]; }