#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>>> ad(N);
for(int i=0; i<M; i++){
ad[U[i]].push_back({V[i], i});
ad[V[i]].push_back({U[i], i});
}
vector<int> up(N, -1), d(N);
vector<int> order;
auto bfs = [&](int s){
vector<int> vis(N);
queue<int> q; q.push(s);
up.assign(N, -1), d.assign(N, 0);
order.clear();
vis[s] = 1;
while(q.size()){
int v = q.front(); q.pop();
order.push_back(v);
for(auto [u, id]: ad[v]){
if(vis[u]) continue;
vis[u] = 1;
d[u] = d[v]+1;
up[u] = id;
q.push(u);
}
}
};
auto ask_depth = [&](int t){
vector<int> w(M);
for(int i=0; i<N; i++){
if(d[i] <= t and up[i] != -1) w[up[i]] = 1;
}
return ask(w);
};
bfs(0);
ll dist = ask_depth(0)/A;
int l = 0, r = N;
while(r-l > 1){
int m = (l+r)/2;
if(ask_depth(m) != dist*B) l = m;
else r = m;
}
int mxdepth = r;
auto ask_vec = [&](vector<pair<int,int>> &vec, int t){
vector<int> w(M);
for(int i=0; i<t; i++)
if(vec[i].second != -1) w[vec[i].second] = 1;
return ask(w);
};
vector<pair<int,int>> susdepth;
for(int i=0; i<N; i++){
if(d[i] == mxdepth) susdepth.push_back({i, up[i]});
}
l = 0, r = susdepth.size();
while(r-l > 1){
int m = (l+r)/2;
if(ask_vec(susdepth, m) == dist*A) l = m;
else r = m;
}
int ans1 = susdepth[l].first;
bfs(ans1);
vector<pair<int,int>> ordersus;
for(int x: order) ordersus.push_back({x, up[x]});
l = 0, r = N;
while(r-l > 1){
int m = (l+r)/2;
if(ask_vec(ordersus, m) != dist*B) l = m;
else r = m;
}
int ans2 = ordersus[l].first;
answer(ans1, ans2);
}
