#include <bits/stdc++.h>
#include "grader.h"
// #include "grader.cpp"
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
#define nl '\n'
int findEgg(int n, vector <pair<int, int>> edges) {
vector<vector<int>> adj(n);
for(auto &[u, v] : edges) {
u--, v--;
adj[u].pb(v);
adj[v].pb(u);
}
queue<int> q;
q.emplace(0);
vector<int> used(n);
used[0] = 1;
vector<int> nod;
while(!q.empty()) {
int v = q.front();
q.pop();
nod.pb(v + 1);
for(auto to : adj[v]) {
if(!used[to]) {
used[to] = 1;
q.emplace(to);
}
}
}
int l = 0, r = (int)nod.size() - 1;
while(l < r) {
int mid = (l + r) >> 1;
vector<int> T;
for(int i = 0; i <= mid; i++) T.pb(nod[i]);
if(query(T)) r = mid;
else l = mid + 1;
}
return nod[l];
}
