#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int findEgg (int N, vector < pair < int, int > > input)
{
vector <vector <int> > gr (N + 1);
for (auto [a, b] : input) {
gr[b].emplace_back (a);
gr[a].emplace_back (b);
}
int timer = 0;
vector <int> in (N + 1);
vector <int> revin (N + 1);
function <void(int,int)> dfs =
[&](int p, int par)->void {
in[p] = ++timer;
revin[in[p]] = p;
for (int& e : gr[p])
if (e != par)
dfs (e, p);
};
dfs (1, -1);
auto ask = [&](int L, int R) {
vector <int> toask;
for (int i = L; i <= R; i++)
toask.emplace_back (revin[i]);
return query (toask);
};
int L = 1, R = timer - 1;
int ans = 0;
while (L <= R) {
int mid = (L + R) / 2;
if (ask (1, mid)) {
R = mid - 1;
ans = mid;
} else
L = mid + 1;
}
return (ans == 0 ? revin[timer] : revin[ans]);
}
