#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;
}
int Ask(vector<int> v){
int k = ask(v);
// for (int i=0;i<v.size();i++){
// if (v[i] == 0)
// cout<<i<<' ';
// }
// cout<<" : "<<k<<endl;
return k;
}
void find_pair(int n, vector<int> u, vector<int> v, int A, int B){
// A = rand() % n, B = rand()
// 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 = -1, r1 = m-1;
while (l1 + 1 < r1){
int md = (l1 + r1) / 2;
// cout<<l1<<" "<<r1<<" "<<md<<" :: ";
if (Ask(color(ord0, md, m)) == B * dst)
l1 = md;
else
r1 = md;
}
// cout<<ord0[r1]<<endl;
// ord1.clear();
dfs(ord0[r1], -1);
// cout<<"done 1"<<endl;
int l2 = -1, r2 = m - 1;
while (l2 + 1 < r2){
int md = (l2 + r2) / 2;
// cout<<l1<<" "<<r1<<" "<<md<<" :: ";
if (Ask(color(ord1, md, m)) == A * dst)
r2 = md;
else
l2 = md;
}
// cout<<ord1[r2]<<endl;
// cout<<"done 2"<<endl;
answer(ord0[r1], ord1[r2]);
}
