#include<bits/stdc++.h>
#include "highway.h"
using namespace std;
struct Edge
{
int b,c;
};
vector<Edge>D[90009];
int n,m;
long long DeafOdl;
vector<int>DeafQuery;
vector<int>BFS(int s)
{
vector<int>ODL(n,-1);
ODL[s]=0;
deque<int>Y={s};
vector<int>W;
while((int)Y.size()>0)
{
const int v=Y[0];
Y.pop_front();
W.push_back(v);
for(auto[som,ind] : D[v])
{
if(ODL[som]==-1)
{
ODL[som]=ODL[v]+1;
Y.push_back(som);
}
}
}
return W;
}
int BinSearch()
{
int l=0,p=n-1;
while(l<p)
{
const int mid=(l+p+1)>>1;
vector<int>Query(m);
for(int i=mid;i<n;i++)
{
for(auto[som,ind] : D[i])
{
Query[ind]=1;
}
}
if(ask(Query)!=DeafOdl)
{
l=mid;
}
else
{
p=mid-1;
}
}
return l;
}
int BinSearch2(int s)
{
vector<int>W=BFS(s);
int l=0,p=n-1;
while(l<p)
{
const int mid=(l+p+1)>>1;
vector<int>Query=DeafQuery;
for(int i=mid;i<n;i++)
{
for(auto[som,ind] : D[W[i]])
{
Query[ind]=1;
}
}
if(ask(Query)!=DeafOdl)
{
l=mid;
}
else
{
p=mid-1;
}
}
return W[l];
}
void find_pair(int N, vector<int>E1, vector<int>E2, int A, int B)
{
n=N;
m=E1.size();
for(int i=0;i<m;i++)
{
D[E1[i]].push_back({E2[i],i});
D[E2[i]].push_back({E1[i],i});
}
DeafOdl=ask(vector<int>(m));
int u=BinSearch();
DeafQuery.resize(m);
for(int i=u+1;i<n;i++)
{
for(auto[som,ind] : D[i])
{
DeafQuery[ind]=1;
}
}
int a=BinSearch2(u);
int b=BinSearch2(a);
if(a>b){swap(a,b);}
//cout<<"a="<<a<<" b="<<b<<" u="<<u<<" DeafOdl="<<DeafOdl<<endl;
answer(a,b);
}
