#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>EE1,EE2;
int O1[90009],O2[90009];
vector<int>BFS(int s, int *O)
{
memset(O,-1,sizeof(O1));
O[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(O[som]==-1)
{
O[som]=O[v]+1;
Y.push_back(som);
}
}
}
return W;
}
int BinSearch()
{
int l=0,p=m-1;
while(l<p)
{
const int mid=(l+p+1)>>1;
vector<int>Query(m);
for(int i=mid;i<m;i++)
{
Query[i]=1;
}
if(ask(Query)!=DeafOdl)
{
l=mid;
}
else
{
p=mid-1;
}
}
return l;
}
int BinSearch2(int s, vector<int>W)
{
int l=0,p=W.size()-1;
while(l<p)
{
const int mid=(l+p+1)>>1;
vector<int>Query(m);
for(int i=mid;i<(int)W.size();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 uA, int uB)
{
n=N;
m=E1.size();
EE1=E1;
EE2=E2;
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();
int aa=EE1[u],bb=EE2[u];
vector<int>AA=BFS(aa,O1);
vector<int>BB=BFS(bb,O2);
vector<int>A,B;
for(int u : AA)
{
if(O1[u]+1==O2[u]){A.push_back(u);}
}
for(int u : BB)
{
if(O2[u]+1==O1[u]){B.push_back(u);}
}
int a=BinSearch2(aa,A);
int b=BinSearch2(bb,B);
if(a>b){swap(a,b);}
//cout<<"a="<<a<<" b="<<b<<" u="<<u<<" DeafOdl="<<DeafOdl<<endl;
answer(a,b);
}
