#include <bits/stdc++.h>
#include "highway.h"
template <class T> using Vec = std::vector<T>;
template <class F> struct RecLambda : private F {
explicit RecLambda(F&& f) : F(std::forward<F>(f)) {}
template <class... Args> decltype(auto) operator() (Args&&... args) const {
return F::operator()(*this, std::forward<Args>(args)...);
}
};
void find_pair(int N, Vec<int> U, Vec<int> V, int A, int B) {
const int M = (int) U.size();
assert(M == N - 1);
Vec<Vec<std::pair<int, int>>> graph(N);
for (int i = 0; i < M; ++i) {
graph[U[i]].emplace_back(V[i], i);
graph[V[i]].emplace_back(U[i], i);
}
Vec<int> pedge(N, -1);
RecLambda([&](auto&& dfs, const int u) -> void {
for (const auto [v, e] : graph[u]) {
if (e != pedge[u]) {
pedge[v] = e;
dfs(v);
}
}
})(0);
const long long len = ask(Vec<int>(M, 0));
Vec<int> cand(N - 1);
std::iota(cand.begin(), cand.end(), 1);
const auto find = [&] {
while (cand.size() > 1) {
const int half = (int) cand.size() / 2;
Vec<int> left(cand.begin(), cand.begin() + half);
Vec<int> right(cand.begin() + half, cand.end());
Vec<int> vec(M, 0);
for (const int u : left) {
vec[pedge[u]] = 1;
}
if (ask(vec) > len) {
cand = std::move(left);
} else {
cand = std::move(right);
}
}
return cand[0];
};
const int root = find();
Vec<int> group(N, 0);
RecLambda([&](auto&& dfs, const int u) -> void {
if (u != root) {
group[u] = 1;
}
for (const auto [v, e] : graph[u]) {
if (e != pedge[u]) {
dfs(v);
}
}
})(root);
const auto [upper, lower] = [&] {
Vec<int> vec(M, 0);
for (int i = 1; i < N; ++i) {
vec[pedge[i]] = group[i];
}
const long long rsp = ask(vec);
const int tmp = (rsp - len) / B;
return std::pair<int, int>(len / A - tmp, tmp);
}();
Vec<int> depth(N);
std::fill(pedge.begin(), pedge.end(), -1);
RecLambda([&](auto&& dfs, const int u) -> void {
for (const auto [v, e] : graph[u]) {
if (e != pedge[u]) {
depth[v] = depth[u] + 1;
pedge[v] = e;
dfs(v);
}
}
})(root);
const int S = [&] {
cand.clear();
for (int i = 0; i < N; ++i) {
if (depth[i] == upper and group[i] == 0) {
cand.push_back(i);
}
}
return find();
}();
const int T = [&] {
if (lower == 0) {
return root;
}
cand.clear();
for (int i = 0; i < N; ++i) {
if (depth[i] == lower and group[i] == 1) {
cand.push_back(i);
}
}
return find();
}();
answer(S, T);
}
