#include <bits/stdc++.h>
#include "grader.h"
// #include "grader.cpp"
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l, int r) {
return l + rng() % (r - l + 1);
}
int findEgg (int n, vector<pair<int, int>> brg){
vector<int> E[n + 1];
for (int i = 0; i < n - 1; i++) {
auto [x, y] = brg[i];
E[x].push_back(y);
E[y].push_back(x);
}
vector<bool> vis(n + 1);
while (true) {
int x = -1, cnt = 0;
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
x = i;
cnt++;
}
}
if (cnt == 1) return x;
vector<int> v;
queue<int> q;
vector<bool> visq(n + 1);
q.push(x); visq[x] = true;
while (!q.empty() && (int)v.size() < (cnt >> 1)) {
int x = q.front(); q.pop();
v.push_back(x);
for (auto i : E[x]) {
if (!vis[i] && !visq[i]) {
q.push(i);
visq[i] = true;
}
}
}
visq.assign(n + 1, false);
for (auto i : v)
visq[i] = true;
bool tr = query(v);
for (int i = 1; i <= n; i++)
if (!vis[i]) vis[i] = (tr ? !visq[i] : visq[i]);
}
}
