#include "highway.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;
#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed
void find_pair(const int N, vector<int> U, vector<int> V, int A, int B) {
const int M = U.size();
i64 defaultDist = ask(vector<int>(M));
int dst = defaultDist / A;
int edgUsed;
{
int s = 0, e = M - 1;
while (s < e) {
int m = (s + e + 1) >> 1;
vector<int> q(M);
fill(q.begin(), q.begin() + m, 1);
i64 d = ask(q);
if (d == defaultDist)
s = m;
else
e = m - 1;
}
edgUsed = s;
}
int u = U[edgUsed];
int v = V[edgUsed];
vector<vector<pi>> graph(N);
for (int i = 0; i < M; i++) {
graph[U[i]].emplace_back(V[i], i);
graph[V[i]].emplace_back(U[i], i);
}
vector<int> vtyp(N), par(N);
vector<i64> distu(N, -1), distv(N, -1);
distu[u] = distv[v] = 0;
{
queue<int> que;
que.emplace(u);
while (!que.empty()) {
auto cur = que.front();
que.pop();
for (auto [t, _] : graph[cur]) {
if (distu[t] == -1) {
distu[t] = distu[cur] + 1;
par[t] = cur;
que.emplace(t);
}
}
}
}
{
queue<int> que;
que.emplace(v);
while (!que.empty()) {
auto cur = que.front();
que.pop();
for (auto [t, _] : graph[cur]) {
if (distv[t] == -1) {
distv[t] = distv[cur] + 1;
par[t] = cur;
que.emplace(t);
}
}
}
}
int us, vs;
for (int i = 0; i < N; i++) {
if (distv[i] > distu[i]) vtyp[i] = 1;
if (distu[i] > distv[i]) vtyp[i] = 2;
}
{
vector<int> hb;
for (int i = 0; i < N; i++)
if (vtyp[i] == 1) hb.emplace_back(i);
auto H = hb.size();
sort(iterall(hb), [&](int l, int r) {
return distu[l] < distu[r];
});
int s = 0, e = H - 1;
while (s < e) {
int m = (s + e + 1) >> 1;
vector<int> q(M);
vector<bool> c(N);
for (int i = m; i < H; i++) c[hb[i]] = true;
for (int i = 0; i < M; i++)
if (c[U[i]] || c[V[i]]) q[i] = 1;
i64 d = ask(q);
if (d == defaultDist)
e = m - 1;
else
s = m;
}
us = hb[s];
}
{
vector<int> hb;
for (int i = 0; i < N; i++)
if (vtyp[i] == 2) hb.emplace_back(i);
auto H = hb.size();
sort(iterall(hb), [&](int l, int r) {
return distv[l] < distv[r];
});
int s = 0, e = H - 1;
while (s < e) {
int m = (s + e + 1) >> 1;
vector<int> q(M);
vector<bool> c(N);
for (int i = m; i < H; i++) c[hb[i]] = true;
for (int i = 0; i < M; i++)
if (c[U[i]] || c[V[i]]) q[i] = 1;
i64 d = ask(q);
if (d == defaultDist)
e = m - 1;
else
s = m;
}
vs = hb[s];
}
answer(us, vs);
}
