#include "highway.h"
int m;
int res[2];
std::vector <int> w;
std::vector <std::pair <int, int> > g[(int)(1e5)], vec;
void dfs(int ve, int pr) {
for (auto to : g[ve]) {
if (to.first == pr)
continue;
vec.push_back(to);
dfs(to.first, ve);
}
}
int poisk(long long total, long long B) {
int l = 0, r = (int)(vec.size()) - 1;
while (l < r) {
int md = (l + r) >> 1;
for (int i = 1; i < (int)(vec.size()); ++i)
w[vec[i].second] = (i <= md);
if (ask(w) == total * B) r = md;
else l = md + 1;
}
return l;
}
void find_pair (int n, std::vector <int> u, std::vector <int> v, int A, int B) {
m = (int)(u.size());
for (int i = 0; i < m; ++i) {
g[u[i]].push_back(std::make_pair(v[i], i));
g[v[i]].push_back(std::make_pair(u[i], i));
}
w.assign(m, 0);
long long total = ask(w) / A;
int s = 0;
for (int _t = 0; _t < 2; ++_t) {
vec.clear();
vec.push_back(std::make_pair(0, -1));
dfs(s, -1);
int p = poisk(total, B);
s = res[_t] = vec[p].first;
}
answer(res[0], res[1]);
}
