#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
int M = U.size();
vector<vector<pair<int, int>>> gr(N);
for (int i = 0; i < M; i++) {
gr[V[i]].push_back({U[i], i});
gr[U[i]].push_back({V[i], i});
}
vector<int> w(M, 0);
ll shrt = ask(w);
int rt = 0, j = 1<<20;
while (j) {
if (rt + j <= N) {
w.assign(M, 0);
for (int i = rt; i < rt + j; i++)
for (auto [u, k] : gr[i])
w[k] = 1;
if (ask(w) == shrt) rt += j;
}
j >>= 1;
}
vector<int> pa(N, -1), cnt(N, 0), ei(N, -1), vis(N, 0);
queue<int> q, lf;
q.push(rt); vis[rt] = 1;
while (q.size()) {
int v = q.front(); q.pop();
for (auto [u, i] : gr[v]) if (!vis[u]) {
cnt[v]++;
vis[u] = 1;
pa[u] = v;
ei[u] = i;
q.push(u);
}
if (!cnt[v]) lf.push(v);
}
vector<int> ord;
while (lf.size()) {
int v = lf.front(); lf.pop();
ord.push_back(v);
if (~pa[v]) if (!--cnt[pa[v]]) lf.push(pa[v]);
}
assert (ord.back() == rt);
int s = 0; j = 1<<20;
while (j) {
if (s + j < N) {
w.assign(M, 0);
for (int i = s; i < s + j; i++) w[ei[ord[i]]] = 1;
if (ask(w) == shrt) s += j;
}
j >>= 1;
}
s = ord[s];
vector<int> dis(N, 1<<30); dis[s] = 0;
vector<int> cand;
vector<vector<int>> from(N);
q.push(s);
while (q.size()) {
int v = q.front(); q.pop();
if (1ll * dis[v] * A == shrt) cand.push_back(v);
for (auto [u, i] : gr[v]) if (dis[u] > dis[v]) {
dis[u] = dis[v] + 1;
from[u].push_back(i);
q.push(u);
}
}
assert (cand.size());
int t = 0;
j = 1<<20;
while (j) {
if (t + j < (int)cand.size()) {
w.assign(M, 0);
for (int i = t; i < t + j; i++)
for (auto k : from[cand[i]])
w[k] = 1;
if (ask(w) == shrt) t += j;
}
j >>= 1;
}
t = cand[t];
answer(s, t);
}
