#include <bits/stdc++.h>
using namespace std;
using i32 = int;
using i64 = long long;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = V<V<T>>;
#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, l, r) for (i32 i = (i32)(l); i < (i32)(r); ++i)
#define PER2(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)
#define PER3(i, l, r) for (i32 i = (i32)(r) - 1; i >= (i32)(l); --i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER(...) OVERRIDE4(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)
#define LEN(x) (i32)size(x)
#define ALL(x) begin(x), end(x)
template <typename T>
bool chmin(T &x, const T &y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
if (x < y) {
x = y;
return true;
}
return false;
}
#include "highway.h"
void find_pair(i32 n, V<i32> u, V<i32> v, i32 _a, i32 _b) {
i64 a = _a, b = _b;
i32 m = LEN(u);
i64 d = ask(V<i32>(m, 0));
i32 path = d / a;
i32 ok = 0, ng = m;
while (ng - ok > 1) {
i32 mid = (ok + ng) / 2;
V<i32> w(m, 0);
fill(w.begin(), w.begin() + mid, 1);
if (ask(w) == d) {
ok = mid;
} else {
ng = mid;
}
}
i32 ed = ok;
VV<pair<i32, i32>> g(n);
REP(i, ed + 1, m) {
g[u[i]].emplace_back(v[i], i);
g[v[i]].emplace_back(u[i], i);
}
i32 r0 = u[ed], r1 = v[ed];
V<i32> dist(n, -1), from(n, -1);
queue<i32> que;
que.push(r0);
que.push(r1);
dist[r0] = 0;
dist[r1] = 0;
from[r0] = r0;
from[r1] = r1;
while (!que.empty()) {
i32 v = que.front();
que.pop();
for (auto [u, e] : g[v]) {
if (dist[u] == -1) {
dist[u] = dist[v] + 1;
from[u] = from[v];
que.push(u);
}
}
}
V<pair<i32, i32>> ss, ts;
REP(i, n) {
if (from[i] != r0) {
continue;
}
for (auto [j, e] : g[i]) {
if (from[j] == r0 && dist[j] == dist[i] - 1) {
ss.emplace_back(dist[i], e);
}
}
}
REP(i, n) {
if (from[i] != r1) {
continue;
}
for (auto [j, e] : g[i]) {
if (from[j] == r1 && dist[j] == dist[i] - 1) {
ts.emplace_back(dist[i], e);
}
}
}
sort(ALL(ss), greater());
sort(ALL(ts), greater());
i32 s = -1, t = -1;
ok = 0;
ng = LEN(ss) + 1;
while (ng - ok > 1) {
i32 mid = (ok + ng) / 2;
V<i32> w(m, 0);
fill(w.begin(), w.begin() + ed, 1);
REP(i, mid) {
w[ss[i].second] = 1;
}
if (ask(w) == d) {
ok = mid;
} else {
ng = mid;
}
}
if (ok == LEN(ss)) {
s = r0;
} else {
i32 e = ss[ok].second;
if (dist[u[e]] > dist[v[e]]) {
s = u[e];
} else {
s = v[e];
}
}
ok = 0;
ng = LEN(ts) + 1;
while (ng - ok > 1) {
i32 mid = (ok + ng) / 2;
V<i32> w(m, 0);
fill(w.begin(), w.begin() + ed, 1);
REP(i, mid) {
w[ts[i].second] = 1;
}
if (ask(w) == d) {
ok = mid;
} else {
ng = mid;
}
}
if (ok == LEN(ts)) {
t = r1;
} else {
i32 e = ts[ok].second;
if (dist[u[e]] > dist[v[e]]) {
t = u[e];
} else {
t = v[e];
}
}
answer(s, t);
}
