#include "bits/stdc++.h" #include "grader.h" #define sz(x) (int)size(x) #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) using namespace std; using ll = long long; using pii = pair<int, int>; const char nl = '\n'; const int INF = 0x3f3f3f3f; const ll LINF = 0x3f3f3f3f3f3f3f3f; int findEgg(int n, vector<pii> bridges) { vector<vector<int>> adj(n + 1); for (int i = 0; i < n - 1; i++) { auto [a, b] = bridges[i]; adj[a].push_back(b); adj[b].push_back(a); } vector<int> ord; auto dfs = [&](auto dfs, int x, int p) -> void { ord.push_back(x); for (int k : adj[x]) if (k != p) { dfs(dfs, k, x); } }; dfs(dfs, 1, -1); auto check = [&](int p) -> bool { vector<int> v; for (int i = 0; i <= p; i++) v.push_back(ord[i]); return query(v); }; int l = -1; // l is bad int r = n - 1; // r is good while (r > l + 1) { int m = (l + r) / 2; check(m) ? r = m : l = m; } return ord[r]; }