#include <iostream>
#include <queue>
#include "highway.h"
using namespace std;
const int N = 1<<17;
int Mn[2][N], Ed[N];
vector<pair<int, int>> nei[N], tree[2][N];
vector<int> ord[2], quer, cpy;
void bfs(int u, int id){
for (int i=0;i<N;i++)
Mn[id][i] = (u != i) * 1e9;
queue<int> Q;
Q.push(u);
while (Q.size() > 0){
u = Q.front(), Q.pop();
for (auto [i, ind] : nei[u]){
if (Mn[id][i] > Mn[id][u] + 1){
tree[id][u].push_back({i, ind});
Mn[id][i] = Mn[id][u] + 1;
Q.push(i);
}
}
}
}
void dfs(int u, int id){
for (auto [i, ind] : tree[id][u]){
if (Mn[id][i] >= Mn[!id][i])
continue;
quer[ind] = 0;
Ed[i] = ind;
dfs(i, id);
}
ord[id].push_back(u);
}
int get(vector<int> v, long long MinCost){
int l = -1, r = v.size() - 1;
while (l + 1 < r){
int md = (l + r) / 2;
cpy = quer;
for (int i=0;i<=md;i++)
cpy[Ed[v[i]]] = 1;
if (ask(cpy) == MinCost)
l = md;
else
r = md;
}
return v[r];
}
void find_pair(int n, vector<int> u, vector<int> v, int A, int B){
int m = u.size();
for (int i=0;i<m;i++){
nei[u[i]].push_back({v[i], i});
nei[v[i]].push_back({u[i], i});
}
quer.resize(m, 1);
long long dst = ask(quer) / B;
int l = -1, r = m - 1;
while (l + 1 < r){
int md = (l + r) / 2;
vector<int> stt(md+1, 0);
stt.resize(m, 1);
if (ask(stt) == dst * A)
r = md;
else
l = md;
}
bfs(u[r], 0);
bfs(v[r], 1);
dfs(u[r], 0);
dfs(v[r], 1);
quer[r] = 0;
int s = get(ord[0], dst * A);
int t = get(ord[1], dst * A);
answer(s, t);
}
