#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<vector<pair<int,int>>> g;
void dist(int s, vector<int>& d, vector<int>& es){
d[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()){
int cur = q.front();
q.pop();
for (pair<int,int> next : g[cur]){
if (d[next.first] == -1){
d[next.first] = d[cur]+1;
es.push_back(next.second);
q.push(next.first);
}
}
}
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
int M = U.size();
g.resize(N);
for (int i=0; i<M; i++){
g[U[i]].push_back({V[i], i});
g[V[i]].push_back({U[i], i});
}
ll len = ask(vector<int>(M, 0))/A;
int l = 0, r = M;
while (l < r-1){
int m = (l+r)/2;
vector<int> w(M, 0);
for (int i=0; i<m; i++) w[i] = 1;
if (ask(w) > (ll)A*len) r = m;
else l = m;
}
int e = l, u = U[e], v = V[e];
//cout << e << endl;
vector<int> du(N, -1), dv(N, -1), deu, dev, eu, ev;
dist(u, du, deu);
dist(v, dv, dev);
for (int x : deu){
if (du[U[x]] < dv[U[x]] && du[V[x]] < dv[V[x]]) eu.push_back(x);
}
reverse(eu.begin(), eu.end());
eu.push_back(e);
for (int x : dev){
if (dv[U[x]] < du[U[x]] && dv[V[x]] < du[V[x]]) ev.push_back(x);
}
reverse(ev.begin(), ev.end());
ev.push_back(e);
/*for (int x : eu) cout << x << " ";
cout << endl;
for (int x : ev) cout << x << " ";
cout << endl;*/
l = 0; r = eu.size();
while (l < r-1){
int m = (l+r)/2;
vector<int> w(M, 1);
for (int x : ev) w[x] = 0;
for (int i=m; i<eu.size(); i++) w[eu[i]] = 0;
if (ask(w) > (ll)A*len) r = m;
else l = m;
}
int s = U[eu[l]];
if (dv[V[eu[l]]] > dv[U[eu[l]]]) s = V[eu[l]];
l = 0; r = ev.size();
while (l < r-1){
int m = (l+r)/2;
vector<int> w(M, 1);
for (int x : eu) w[x] = 0;
for (int i=m; i<ev.size(); i++) w[ev[i]] = 0;
if (ask(w) > (ll)A*len) r = m;
else l = m;
}
int t = U[ev[l]];
if (du[V[ev[l]]] > du[U[ev[l]]]) t = V[ev[l]];
answer(s, t);
}
