#include "highway.h"
#include <cstdio>
#include <cassert>
const int MN = 9e4+10;
const int MM = 1.3e5+10;
using ll = long long;
struct edg
{
public:
int n, i;
};
std::vector<edg> a[MN];
int pre[MN], ctr, pid[MN], ord[MN], d[MN], post[MN];
void dfs(int n, int p=-1)
{
ord[ctr] = n;
pre[n]=ctr++;
for(int i=0;i<(int)a[n].size();++i)
{
if(a[n][i].n == p)
{
a[n].erase(a[n].begin()+i);
--i;
continue;
}
d[a[n][i].n]=d[n]+1;
pid[a[n][i].n]=a[n][i].i;
dfs(a[n][i].n, n);
}
post[n]=ctr;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
int M = U.size();
for(int i=0;i<M;++i)
{
a[U[i]].push_back({V[i], i});
a[V[i]].push_back({U[i], i});
}
std::vector<int> w(M, 0);
ll dist_raw = ask(w); // -1
int dist = (int)(dist_raw/A);
dfs(0);
assert(ctr == N);
int lca=-1;
{ // -17
int l=0, r=N;
for(;r-l>1;)
{
int m=l+(r-l)/2;
w.assign(M, 0);
for(int i=l;i<m;++i)
for(auto x:a[ord[i]])
w[x.i]=1;
if(ask(w)>dist_raw)
r = m;
else
l = m;
}
lca=ord[l];
}
int S;
{ // -17
int l=pre[lca]+1;
int r=post[lca];
for(;r-l>1;)
{
int m=l+(r-l)/2;
w.assign(M, 0);
for(int i=m;i<r;++i)
w[pid[ord[i]]]=1;
//printf("%d %d %d %lld\n", ord[l], ord[m], ord[r], ask(w));
if(ask(w)>dist_raw)
l = m;
else
r = m;
//printf("%d %d\n", l, r);
}
S = ord[l];
}
int T;
{ // -17
std::vector<int> cand;
for(int i=pre[lca];i<pre[S];++i)
if(d[ord[i]] + d[S] - 2*d[lca] == dist)
cand.push_back(ord[i]);
int l=0, r=cand.size(); // can binsearch from left or right now
for(;r-l>1;)
{
int m=l+(r-l)/2;
w.assign(M, 0);
for(int i=l;i<m;++i)
w[pid[cand[i]]]=1;
if(ask(w) > dist_raw)
r = m;
else
l = m;
}
T = cand[l];
}
printf("%d %d\n", S, T);
answer(S, T);
}
