#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];
ll dep[MAXN];
vll ord;
void dfs (ll u) {
vis[u] = true;
for (auto [v, id] : adjT[u]) {
if (vis[v]) continue;
dep[v] = dep[u]+1;
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 raw = ask(vi(m, 0));
ll dis = raw/a;
vi askMask(m, -15);
ll src1 = -15, src2 = -15;
{ll l = -1, r = m-1;
while (l+1 < r) {
ll mid = (l+r)>>1;
vi vask(m, 0);
for (ll i = 0; i <= mid; i++) vask[i] = 1;
if (ask(vask) == raw)
l = mid;
else
r = mid;
}
askMask = vi(m, 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 });
askMask[r] = 0;
while (q.size()) {
ll u = q.front(); q.pop();
for (auto [v, id] : adj[u]) {
if (vis[v] || id <= l) continue;
vis[v] = true; q.push(v);
// cerr << u << ' ' << v << '\n';
adjT[u].push_back({ v, id });
adjT[v].push_back({ u, id });
askMask[id] = 0;
}
}}
dep[src1] = 0;
dfs(src1);
// for (ll i : askMask) cout << i << ' ';
// cout << " askMask\n";
// for (ll i : ord) cout << i << ' ';
// cout << " ord\n";
// for (ll i : ord) cout << toPar[i] << ' ';
// cout << " par[ord]\n";
ll u1 = -15, u2 = -15;
{ll l = -1, r = ord.size();
// l es normal
// r lo corta
while (l+1 < r) {
ll mid = (l+r)>>1;
vi vask(askMask.begin(), askMask.end());
for (ll i = 0; i <= mid; i++) vask[toPar[ord[i]]] = 1;
if (ask(vask) == raw)
l = mid;
else
r = mid;
}
u1 = ord[r];}
// cout << u1 << " u1\n";
fill(vis, vis+MAXN, false);
ord.clear();
dep[u1] = 0;
dfs(u1);
{vll nord;
for (ll i : ord)
if (dep[i] == dis) nord.push_back(i);
swap(ord, nord);}
// for (ll i : ord) cout << i << ' ';
// cout << " ord\n";
{ll l = -1, r = ord.size();
// l es normal
// r lo corta
while (l+1 < r) {
ll mid = (l+r)>>1;
vi vask(askMask.begin(), askMask.end());
for (ll i = 0; i <= mid; i++) vask[toPar[ord[i]]] = 1;
if (ask(vask) == raw)
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);
}
