#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int findEgg(int n, vector<pair<int, int>> edges) {
vector<vector<int>> g(n + 1);
for (auto p : edges) {
int u = p.first;
int v = p.second;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> order;
function<void(int, int)> dfs = [&](int u, int p) {
order.push_back(u);
for (int v : g[u]) {
if (v != p) {
dfs(v, u);
}
}
};
dfs(1, 0);
int m = (int) order.size();
int lo = 0, hi = m - 1;
auto ok = [&](int x) {
vector<int> c;
for (int i = 0; i <= x; i++) {
c.push_back(order[i]);
}
return query(c);
};
while (lo < hi) {
int mid = (lo + hi) / 2;
if (ok(mid)) {
hi = mid;
}
else {
lo = mid + 1;
}
}
return order[lo];
}
