#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<array<int, 2>>> adj;
vector<array<int, 2>> to_ask;
int n, m, dp, A, B;
void dfs (int u = 0, int p = -1, int d = 1) {
for (auto &v : adj[u]) {
if (v[0] ^ p) {
if (d == dp) {
vector<int> ak(m, 0);
ak[v[1]] = 1;
to_ask.push_back(v);
}
else {
dfs(v[0], u, d + 1);
}
}
}
}
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});
}
dp = ask(vector<int>(m, 0)) / A;
dfs();
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) != dp * 1LL * A) {
r = mid;
}
else {
l = mid + 1;
}
}
answer(0, to_ask[l][0]);
}
