#include <bits/stdc++.h> #include "grader.h" using namespace std; vector<vector<int>> v; vector<int> ord, vis; int n, t; void dfs(int node) { ord[++t] = node; vis[node] = 1; for(int son : v[node]) { if(!vis[son]) { dfs(son); } } } int check(int cnt) { if(cnt > n) { return 1; } vector<int> q; for(int i=1; i<=cnt; ++i) { q.push_back(ord[i]); } return query(q); } int findEgg(int N, vector<pair<int, int>> bridges) { n = N; v.assign(n+1, vector<int>()); ord.assign(n+1, 0); vis.assign(n+1, 0); t = 0; for(auto [a, b] : bridges) { v[a].push_back(b); v[b].push_back(a); } dfs(1); int ans = 0; for(int bit = 30 - __builtin_clz(n); bit >= 0; --bit) { if(!check(ans + (1<<bit))) { ans |= (1<<bit); } } return ord[ans+1]; }