#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) { 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 st = 1, dr = n, mij; while(st <= dr) { mij = (st+dr>>1); if(check(mij)) { dr = mij - 1; } else { st = mij + 1; } } return ord[dr+1]; }