#include <bits/stdc++.h> #include "grader.h" using namespace std; int findEgg (int N, vector<pair<int, int>> bridges) { vector<int> adj[600]; for(auto [u, v] : bridges){ adj[u].push_back(v); adj[v].push_back(u); } vector<int> Q; bitset<600> can; can.set(); int sz = N; auto bfs = [&](int x){ // cerr << "TEST\n"; bitset<600> vis; queue<int> q; q.push(x); vis[x] = 1; while(!q.empty()){ int u = q.front(); q.pop(); Q.push_back(u); if(Q.size() == sz) break; for(int v : adj[u]){ if(vis[v] || !can[v]) continue; vis[v] = 1; q.push(v); } } }; while(sz > 1){ // cerr << sz << ' '; for(int i = 1; i <= N; ++i){ if(can[i]){ bfs(i); break; } } // cerr << "DBG : "; // cerr << sz << '\n'; // for(auto i : Q) cerr << i << ' '; // cerr << '\n'; if(Q.empty()) break; if(query(Q)){ can.reset(); for(int x : Q) can[x] = 1; // cerr << "TRUE\n"; }else{ for(int x : Q) can[x] = 0; // cerr << "FALSE\n"; } sz = (sz+1)/2; Q.clear(); } // cerr << "Ans list : "; // for(int x : Q) cerr << x << ' '; // for(int i = 1; i <= N; ++i){ // if(can[i] == 1) cerr << i << ' '; // } // cerr << '\n'; for(int i = 1; i <= N; ++i){ if(can[i] && query({i})) return i; } return -1; }