#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=1e5+5;
ll m, res, l, r, ls, rs, vs[nx], cnt, nl, nr;
pair<int, int> id[nx], ans;
vector<int> qrs, used;
vector<pair<int, int>> d[nx], t[nx];
queue<int> q;
void dfs(int u)
{
for (auto [v, idx]:t[u]) id[++cnt]={v, idx}, dfs(v);
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
m=U.size();
qrs.resize(U.size());
for (int i=0; i<m; i++) qrs[i]=0, d[U[i]].push_back({V[i], i}), d[V[i]].push_back({U[i], i});
res=ask(qrs);
l=0; r=m-1;
while (l<r)
{
int md=(l+r)/2;
for (int i=0; i<m; i++) qrs[i]=i>md;
if (ask(qrs)!=res) l=md+1;
else r=md;
}
ls=U[l];
rs=V[l];
//cout<<"edge "<<ls<<' '<<rs<<'\n';
vs[ls]=vs[rs]=1;
used.push_back(l);
q.push(ls);
q.push(rs);
while (!q.empty())
{
auto u=q.front();
q.pop();
for (auto [v, idx]:d[u]) if (!vs[v]) t[u].push_back({v, idx}), used.push_back(idx), vs[v]=1, q.push(v);
}
//cout<<"edge "<<ls<<' '<<rs<<'\n';
//for (int i=0; i<m; i++) cout<<used[i]<<' ';
//cout<<'\n';
id[0]={ls, l};
dfs(ls);
nl=0; nr=cnt;
for (int i=0; i<m; i++) qrs[i]=1;
while (nl<nr)
{
int md=(nl+nr+1)/2;
for (auto x:used) qrs[x]=0;
for (int i=md; i<=nr; i++) qrs[id[i].second]=1;
if (ask(qrs)!=res) nl=md;
else nr=md-1;
}
ans.first=id[nl].first;
id[0]={rs, l};
cnt=0;
dfs(rs);
nl=0; nr=cnt;
while (nl<nr)
{
int md=(nl+nr+1)/2;
for (auto x:used) qrs[x]=0;
for (int i=md; i<=nr; i++) qrs[id[i].second]=1;
if (ask(qrs)!=res) nl=md;
else nr=md-1;
}
ans.second=id[nl].first;
answer(ans.first, ans.second);
}
/*
3 3 1 2 0 1
0 1
1 2
2 0
4 4 1 3 1 3
0 1
0 2
0 3
1 2
3 6 1 2 1 2
0 1
0 1
1 2
1 2
2 0
2 0
*/
