#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
int findEgg(int n,vector<pair<int,int>>g){
vector<int>f[n+5];
for(auto [a,b]:g){
f[a].pb(b);
f[b].pb(a);
}
queue<int>q;
q.push(1);
vector<int>v;
vector<bool>used(n+5,false);
used[1]=true;
while(!q.empty()){
int x=q.front();
q.pop();
v.pb(x);
for(int y:f[x]){
if(!used[y]){
used[y]=true;
q.push(y);
}
}
}
int lo=0,hi=n-1;
while(lo<hi){
int mid=(lo+hi)/2;
vector<int>ask;
for(int i=0;i<=mid;i++){
ask.pb(v[i]);
}
if(query(ask)==1){
hi=mid;
}
else{
lo=mid+1;
}
}
return v[lo];
}
