#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<array<int, 2>>> adj;
vector<array<int, 2>> to_ask;
vector<int> ak;
int n, m, A, B, dp;
long long W;
void dfs (int u, int p, int d = 1) {
for (auto &v : adj[u]) {
if (v[0] ^ p) {
if (d == dp) {
to_ask.push_back(v);
}
else {
dfs(v[0], u, d + 1);
}
}
}
}
void dfs2 (int u, int p) {
for (auto &v : adj[u]) {
if (v[0] ^ p) {
ak[v[1]] = 1;
dfs2(v[0], u);
}
}
}
int first () {
int l = 0, r = m - 1;
W = ask(vector<int>(m, 0));
while (l < r) {
int mid = (l + r) / 2;
vector<int> ak(m, 0);
fill(ak.begin(), ak.begin() + mid + 1, 1);
if (ask(ak) != W) {
r = mid;
}
else {
l = mid + 1;
}
}
return l;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
n = N;
m = U.size();
::A = A;
::B = B;
adj.assign(n, {});
for (int i = 0; i < m; ++i) {
adj[U[i]].push_back({V[i], i});
adj[V[i]].push_back({U[i], i});
}
int f = first();
int u = U[f], v = V[f];
ak.assign(m, 0);
dfs2(u, v);
long long WE = ask(ak);
int s = W / A;
auto go = [&] (int u, int v, int dp) {
if (!dp) {
return u;
}
::dp = dp;
to_ask.clear();
dfs(u, v);
int l = 0, r = to_ask.size() - 1;
while (l < r) {
int mid = (l + r) / 2;
vector<int> ak(m, 0);
for (int i = 0; i <= mid; ++i) {
ak[to_ask[i][1]] = 1;
}
if (ask(ak) != s * 1LL * A) {
r = mid;
}
else {
l = mid + 1;
}
}
return to_ask[l][0];
};
for (int i = 0; i <= s; ++i) {
if (i * 1LL * A + (s - i) * 1LL * B == WE) {
return answer(go(u, v, s - i), go(v, u, i - 1));
}
}
assert(0);
}
