#include "highway.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 2e5+10;
vector<vector<pii> > graph;
int upar[MAXN];
int ud[MAXN];
int uque[MAXN];
int vpar[MAXN];
int vd[MAXN];
int vque[MAXN];
int chk[MAXN];
int uver[MAXN];
int vver[MAXN];
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
int M = U.size();
vector<int> w(M,0);
const ll shortest_path = ask(w);
ll cur_path = 0;
int idx = 0;
for(int i=16;i>=0;i--){
if((idx|(1<<i))>=M)continue;
for(int j=0;j<(idx|(1<<i));j++){
w[j] = 1;
}
for(int j=(idx|(1<<i));j<M;j++){
w[j] = 0;
}
cur_path = ask(w);
if(!(shortest_path^cur_path)){
idx|=(1<<i);
}
}
int u = U[idx];
int v = V[idx];
graph = vector<vector<pii> > (N);
for(int i=0;i<M;i++){
graph[U[i]].push_back(pii(V[i],i));
graph[V[i]].push_back(pii(U[i],i));
}
fill(ud,ud+N,-1);
fill(upar,upar+N,-1);
fill(vd,vd+N,-1);
fill(vpar,vpar+N,-1);
int L = 0;
int R = 0;
int here,there;
ud[u] = 0;
uque[0] = u;
while(L<=R){
here = uque[L]; L++;
for(int i=0;i<(int)graph[here].size();i++){
there = graph[here][i].f;
if(ud[there]!=-1)continue;
ud[there] = ud[here]+1;
upar[there] = graph[here][i].s;
R++;
uque[R] = there;
}
}
assert(R==(N-1));
vd[v] = 0;
vque[0] = v;
L = 0;
R = 0;
while(L<=R){
here = vque[L]; L++;
for(int i=0;i<(int)graph[here].size();i++){
there = graph[here][i].f;
if(vd[there]!=-1)continue;
vd[there] = vd[here]+1;
vpar[there] = graph[here][i].s;
R++;
vque[R] = there;
}
}
assert(R==(N-1));
chk[idx] = 1;
int cntu = 0,cntv = 0;
uver[0] = u;
for(int i=1;i<N;i++){
here = uque[i];
if(ud[here]<vd[here]){
chk[upar[here]] = 1;
cntu++;
uver[cntu] = here;
}
}
vver[0] = v;
for(int i=1;i<N;i++){
here = vque[i];
if(vd[here]<ud[here]){
chk[vpar[here]] = 1;
cntv++;
vver[cntv] = here;
}
}
for(int i=0;i<M;i++){
w[i] = chk[i]^1;
}
int idu = 0;
for(int t=16;t>=0;t--){
if((idu|(1<<t))>cntu)continue;
for(int i=idu|(1<<t);i<=cntu;i++){
here = uver[i];
w[upar[here]] = 1;
}
cur_path = ask(w);
if(cur_path^shortest_path){
idu|=(1<<t);
}
for(int i=idu|(1<<t);i<=cntu;i++){
here = uver[i];
w[upar[here]] = 0;
}
}
int idv = 0;
for(int t=16;t>=0;t--){
if((idv|(1<<t))>cntv)continue;
for(int i=idv|(1<<t);i<=cntv;i++){
here = vver[i];
w[vpar[here]] = 1;
}
cur_path = ask(w);
if(cur_path^shortest_path){
idv|=(1<<t);
}
for(int i=idv|(1<<t);i<=cntv;i++){
here = vver[i];
w[vpar[here]] = 0;
}
}
int anss = uver[idu];
int anst = vver[idv];
answer(anss,anst);
return;
}
