#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];
}
