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