#include <bits/stdc++.h>
#define ff first
#define ss second
#include "highway.h"
using namespace std;
using cat = long long;
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
int M = U.size();
vector<int> vq(M, 1);
cat L = ask(vq) / B;
// find edge on shortest path
int el = 0, er = M;
while(er - el > 1) {
int em = (el + er + 1) / 2;
for(int i = 0; i < em; i++) vq[i] = 0;
for(int i = em; i < M; i++) vq[i] = 1;
cat ans = ask(vq);
if(ans == L * A) er = em;
else el = em;
}
vector< vector< pair<int, int> > > G(N);
for(int i = 0; i <= el; i++) {
G[U[i]].push_back({V[i], i});
G[V[i]].push_back({U[i], i});
}
// BFS graph for 2
queue<int> q;
vector<int> dep2(N, -1), v2;
vector< vector<int> > e2_in(N);
q.push(U[el]);
dep2[U[el]] = 0;
while(!q.empty()) {
v2.push_back(q.front());
for(auto e: G[q.front()]) if(dep2[e.ff] == -1) {
dep2[e.ff] = dep2[q.front()]+1;
q.push(e.ff);
}
q.pop();
}
for(int i = 0; i <= el; i++) {
if(dep2[U[i]] > dep2[V[i]]) e2_in[U[i]].push_back(i);
if(dep2[U[i]] < dep2[V[i]]) e2_in[V[i]].push_back(i);
}
int v2l = 0, v2r = v2.size();
while(dep2[v2[v2r-1]] > L) v2r--;
while(v2r-v2l > 1) {
int v2m = (v2l + v2r + 1) / 2;
for(int i = 0; i < M; i++) vq[i] = 1;
for(int i = 0; i < v2m; i++)
for(auto e: e2_in[v2[i]]) vq[e] = 0;
cat ans = ask(vq);
if(ans == L * A) v2r = v2m;
else v2l = v2m;
}
int S = v2[v2l];
vector<bool> bl(N, false);
vector<int> e_bl;
int cur = S;
while(dep2[cur] > 0) {
bl[cur] = true;
for(auto e: G[cur]) if(dep2[e.ff] == dep2[cur]-1) {
e_bl.push_back(e.ss);
cur = e.ff;
break;
}
}
// BFS graph for 1
vector<int> dep1(N, -1), v1;
vector< vector<int> > e1_in(N);
q.push(U[el]);
dep1[U[el]] = 0;
while(!q.empty()) {
v1.push_back(q.front());
for(auto e: G[q.front()]) if(!bl[e.ff] && dep1[e.ff] == -1) {
dep1[e.ff] = dep1[q.front()]+1;
q.push(e.ff);
}
q.pop();
}
for(int i = 0; i <= el; i++) if(!bl[U[i]] && !bl[V[i]]) {
if(dep1[U[i]] > dep1[V[i]]) e1_in[U[i]].push_back(i);
if(dep1[U[i]] < dep1[V[i]]) e1_in[V[i]].push_back(i);
}
int v1l = 0, v1r = v1.size();
while(dep1[v1[v1r-1]] > L-dep2[S]) v1r--;
while(v1r-v1l > 1) {
int v1m = (v1l + v1r + 1) / 2;
for(int i = 0; i < M; i++) vq[i] = 1;
for(auto e: e_bl) vq[e] = 0;
for(int i = 0; i < v1m; i++)
for(auto e: e1_in[v1[i]]) vq[e] = 0;
cat ans = ask(vq);
if(ans == L * A) v1r = v1m;
else v1l = v1m;
}
int T = v1[v1l];
answer(S, T);
}
