#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int M = 90000 + 3;
vector<int> nei[M];
int dis[M][2];
void bfs(int u,int id,int n)
{
for (int i=0;i<n;i++) dis[i][id]=M;
queue<int> q;
q.push(u), dis[u][id]=0;
while (!q.empty())
{
int u=q.front();
q.pop();
for (int i:nei[u])
if (dis[i][id]>dis[u][id]+1)
dis[i][id]=dis[u][id]+1, q.push(i);
}
}
void find_pair(int n, vector<int> u, vector<int> v, int A, int B)
{
int m=u.size();
for (int i=0;i<m;i++)
nei[u[i]].push_back(v[i]), nei[v[i]].push_back(u[i]);
ll mn=ask(vector<int> (m));
int s=-1, e=m;
while (s+1<e)
{
int mid=(s+e)/2;
vector<int> v1(m,1);
for (int i=0;i<=mid;i++)
v1[i]=0;
if (ask(v1)==mn)
e=mid;
else
s=mid;
}
int x=v[e], y=u[e];
bfs(x,0,n), bfs(y,1,n);
vector<pair<int,int>> a[2];
for (int i=0;i<n;i++)
if (dis[i][0]<dis[i][1]) a[0].push_back({dis[i][0],i});
else if(dis[i][1]<dis[i][0]) a[1].push_back({dis[i][1],i});
int as[2];
for (int j=0;j<=1;j++)
{
sort(a[j].begin(),a[j].end());
int ind[n];
for (int i=0;i<n;i++) ind[i]=-1;
for (int i=0;i<a[j].size();i++) ind[a[j][i].second]=i;
int s=-1, e=a[j].size();
while (s+1<e)
{
vector<int> v1(m);
int mid=(s+e)/2;
for (int i=0;i<m;i++)
{
if (~ind[u[i]] && ~ind[v[i]])
if (max(ind[u[i]],ind[v[i]])>mid) v1[i]=1;
}
if (ask(v1)==mn)
e=mid;
else
s=mid;
}
as[j]=a[j][e].second;
}
answer(as[0],as[1]);
}
