#include <iostream>
#include <vector>
#include "highway.h"
using namespace std;
const int Sz = 1<<17;
vector<pair<int, int>> nei[Sz];
int Ed[Sz];
vector<int> ord0, ord1;
void dfs(int u, int p){
// cout<<u<<" "<<p<<endl;
for (auto [i, id] : nei[u]){
if (i == p)
continue;
Ed[i] = id;
ord1.push_back(i);
dfs(i, u);
ord0.push_back(i);
}
}
vector<int> color(vector<int> &v, int ind, int m){
vector<int> ans(m, 1);
for (int i=0;i<=ind;i++)
ans[Ed[v[i]]] = 0;
return ans;
}
void find_pair(int n, vector<int> u, vector<int> v, int A, int B){
// cout<<"done"<<endl;
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});
}
// cout<<"done"<<endl;
dfs(0, 0);
int dst = ask(vector<int> (m, 0)) / A;
// cout<<"done 0"<<endl;
int l1 = 0, r1 = m;
while (l1 + 1 < r1){
int md = (l1 + r1) / 2;
if (ask(color(ord0, md, m)) == B * dst)
l1 = md;
else
r1 = md;
}
// cout<<"done 1"<<endl;
int l2 = -1, r2 = m - 1;
while (l2 + 1 < r2){
int md = (l2 + r2) / 2;
if (ask(color(ord1, md, m)) == A * dst)
r2 = md;
else
l2 = md;
}
// cout<<"done 2"<<endl;
answer(ord0[l1], ord1[r2]);
}
