#include <bits/stdc++.h>
#include "grader.h"
#define vt vector
#define pii pair<int, int>
#define fi first
#define sc second
using namespace std;
int findEgg (int n, vt<pii> edges) {
vt<int> path(n + 1);
vt<vt<int>> adj(n + 1);
int timeDFS = 0;
for (auto& edge : edges) {
adj[edge.fi].emplace_back(edge.sc);
adj[edge.sc].emplace_back(edge.fi);
}
auto dfs = [&] (auto& dfs, int u, int p) -> void {
path[++timeDFS] = u;
for (int& v : adj[u]) {
if (v != p) dfs(dfs, v, u);
}
};
dfs(dfs, 1, 1);
int lo = 1, hi = n;
while (lo < hi) {
int mid = (lo + hi) >> 1;
vt<int> v;
for (int i = 1; i <= mid; ++i)
v.emplace_back(path[i]);
if (query(v)) hi = mid;
else lo = mid + 1;
}
return path[lo];
}
