#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
using ii = pair <ll, ll>;
using vii = vector <ii>;
const ll MAXN = 1.3E5+16;
vii adj[MAXN];
vii adjT[MAXN];
bool vis[MAXN];
ll toPar[MAXN];
vll ord;
void dfs (ll u) {
vis[u] = true;
for (auto [v, id] : adjT[u]) {
if (vis[v]) continue;
dfs(v);
toPar[v] = id;
}
ord.push_back(u);
}
void find_pair (int n, vi us, vi vs, int a, int b) {
ll m = us.size();
for (ll i = 0; i < m; i++) {
adj[us[i]].push_back({ vs[i], i });
adj[vs[i]].push_back({ us[i], i });
}
ll dis = ask(vi(m, 0));
vi askMask(m, 0);
ll src1 = -15, src2 = -15;
{ll l = -1, r = m-1;
while (l+1 < r) {
ll mid = (l+r)>>1;
askMask = vi(m, 0);
for (ll i = 0; i <= mid; i++) askMask[i] = 1;
if (ask(askMask) == dis)
l = mid;
else
r = mid;
}
askMask = vi(m, 0);
for (ll i = 0; i <= l; i++) askMask[i] = 1;
src1 = us[r];
src2 = vs[r];
queue <ll> q;
vector <char> vis(n, false);
vis[src1] = true; q.push(src1);
vis[src2] = true; q.push(src2);
adjT[src1].push_back({ src2, r });
adjT[src2].push_back({ src1, r });
while (q.size()) {
ll u = q.front(); q.pop();
for (auto [v, id] : adj[u]) {
if (vis[v]) continue;
vis[v] = true; q.push(v);
adjT[u].push_back({ v, id });
adjT[v].push_back({ u, id });
}
}}
dfs(0);
// for (ll i : ord) cout << i << ' ';
// cout << " ord\n";
ll u1 = -15, u2 = -15;
{ll l = -1, r = m-1;
// l es normal
// r lo corta
while (l+1 < r) {
ll mid = (l+r)>>1;
vi vask = askMask;
for (ll i = 0; i <= mid; i++) vask[toPar[ord[i]]] = 1;
if (ask(vask) == dis)
l = mid;
else
r = mid;
}
u1 = ord[r];}
fill(vis, vis+MAXN, false);
ord.clear();
dfs(u1);
// for (ll i : ord) cout << i << ' ';
// cout << " ord\n";
{ll l = -1, r = m-1;
// l es normal
// r lo corta
while (l+1 < r) {
ll mid = (l+r)>>1;
vi vask = askMask;
for (ll i = 0; i <= mid; i++) vask[toPar[ord[i]]] = 1;
if (ask(vask) == dis)
l = mid;
else
r = mid;
}
// cout << "l, r: " << l << ' ' << r << '\n';
// cout << "ord[l, r]: " << ord[l] << ' ' << ord[r] << '\n';
u2 = ord[r];}
// cout << "u1 " << u1 << '\n';
// cout << "u2 " << u2 << '\n';
answer(u1, u2);
}
