#include <bits/stdc++.h>
using namespace std;
#define pub push_back
#define fi first
#define se second
using pii=pair<int,int>;
using vi=vector<int>;
using vpii=vector<pii>;
using vb=vector<bool>;
using vvi=vector<vi>;
int findEgg(int n, vpii a)
{
#include "grader.h"
vi b; b.reserve(n);
vvi c(n+1);
for (auto i:a)
{
c[i.fi].pub(i.se);
c[i.se].pub(i.fi);
}
// return 0;
queue<int> q; vb vis(n+1);
q.push(1);
while (!q.empty())
{
int x{q.front()};
q.pop(); b.pub(x);
vis[x]=1;
for (auto i:c[x])
{
if (!vis[i])
{
q.push(i);
}
}
}
return 0;
int l{-1},r{n};
while (l<r-1)
{
int mid{((l+r)>>1)};
if (query(vi(b.begin(),b.begin()+mid)))
{
r=mid;
}
else
{
l=mid;
}
}
return b[r];
}
