#include <bits/stdc++.h> #include "grader.h" using namespace std; int findEgg (int n, vector < pair < int, int > > bridges){ int x = n; int can[n + 1] = {}, in[n + 1] = {}; vector < int > ver; vector < int > g[n + 1]; fill(can, can + n + 1, 1); for(auto [x, y] : bridges) g[x].push_back(y), g[y].push_back(x); function < void(int, int) > dfs = [&](int v, int p){ if(!x) return; ver.push_back(v); if(can[v]) in[v] = 1, x--; for(int u : g[v]) if(u != p) dfs(u, v); }; while(x > 1){ int val = x; ver.clear(); for(int i = 1; i <= n; i++) in[i] = 0; x >>= 1, dfs(1, -1); // cout << "ver "; // for(int v : ver) cout << v << ' '; // cout << "<--- " << query(ver) << '\n'; if(query(ver)){ for(int i = 1; i <= n; i++) can[i] &= in[i]; x = val / 2; } else{ for(int i = 1; i <= n; i++) can[i] &= (in[i] ^ 1); x = val - val / 2; } // cout << "case " << val << ' ' << x << '\n'; // for(int i = 1; i <= n; i++) cout << can[i] << ' '; // cout << '\n'; } for(int i = 1; i <= n; i++) if(can[i]) return i; return -1; }