#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);
for (auto i:a)
{
c[i.fi-1].pub(i.se-1);
c[i.se-1].pub(i.fi-1);
}
// return 0;
queue<int> q; vb vis(n);
q.push(0); vis[0]=1;
while (!q.empty())
{
int x{q.front()};
q.pop(); b.pub(x+1);
for (auto i:c[x])
{
if (!vis[i])
{
vis[i]=1;
q.push(i);
}
}
}
// return n;
int l{0},r{n-1};
if (query(vi(b.begin(),b.begin()+l+1)))
{
return b[l];
}
if (query(vi(b.begin(),b.begin()+r+1)))
{
return b[r];
}
while (l<r-1)
{
int mid{((l+r)>>1)};
if (query(vi(b.begin(),b.begin()+mid+1)))
{
r=mid;
}
else
{
l=mid;
}
}
return b[r];
}
