#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define pb push_back
// #define int long long
#define fi first
#define se second
const int N1 = 3e5 + 5, M = 1e9 + 7, LG = 20;
int n , A[N1] , x , mo , ANS = -1;
vector<int> lis[N1] , up;
bool vi[N1];
int f = 4;
void dfs(int v , int par , int N){
if (ANS >= 0) return;
up.pb(v);
mo--;
if (!mo){
bool x = query(up);
// cout << v << ' ' << x << endl;
if (x){
vector<int> p;
for (int i : up){
if (!vi[i]){
p.pb(i);
// cout << i << ' ';
}
}
// cout << endl;
swap(p , up);
int l = 0 , r = up.size();
while(l + 1 < r){
int mid = (l+r)/2;
vector<int> k;
for (int i=mid ; i<r ; i++){
k.pb(up[i]);
}
bool x = query(k);
if (x){
l = mid;
}else{
r = mid;
}
}
ANS = up[l];
// cout << l << endl;
return;
}else{
for (int i : up) vi[i] = 1;
mo = N/f;
if (!mo) mo = 1;
// cout << "Don " << mo << endl;
f *= 2;
}
}
for (int u : lis[v]){
if (u==par) continue;
dfs(u , v , N);
}
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
for (int i=0 ; i<=N ; i++){
vi[i] = 0;
lis[i].clear();
}
for (int i=0 ; i<N-1 ; i++){
lis[bridges[i].fi].pb(bridges[i].se);
lis[bridges[i].se].pb(bridges[i].fi);
}
mo = N/2;
ANS = -1;
up.clear();
f = 4;
// cout << N << endl;
dfs(1 , 0 , N);
// cout << ANS << endl;
return ANS;
}
