#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
using ll = long long;
void find_pair(int n, vector<int> A, vector<int> B, int a, int b) {
int m = (int) B.size();
const ll val = ask(vector<int>(m));
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < m; ++i) {
g[A[i]].push_back({B[i], i});
g[B[i]].push_back({A[i], i});
}
function<int(vector<int>)> bin_search = [&](const vector<int> &v) -> int {
if (v.size() == 1) {
return v[0];
}
int sz = (int) v.size();
assert(sz > 0);
int mid = int(v.size() >> 1);
vector<int> L(mid), R(sz - mid);
for (int i = 0; i < mid; ++i) {
L[i] = v[i];
}
for (int i = mid; i < sz; ++i) {
R[i - mid] = v[i];
}
vector<int> nxt(m, 0);
for (int x: R) {
for (auto [to, i]: g[x]) {
nxt[i] = 1;
}
}
ll now = ask(nxt);
if (now == val) {
return bin_search(L);
} else {
return bin_search(R);
}
};
auto solve = [&](int s) {
//solves for tree with known S
int len = val / a;
vector<int> depth(n, -1);
depth[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto [to, i]: g[v]) {
if (depth[to] == -1) {
depth[to] = depth[v] + 1;
q.push(to);
}
}
}
vector<int> canditates;
for (int i = 0; i < n; ++i) {
if (depth[i] == len) {
canditates.push_back(i);
}
}
answer(s, bin_search(canditates));
};
vector<int> u(n);
iota(u.begin(), u.end(), 0);
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
if (a == 1 && b == 2)
shuffle(u.begin(), u.end(), rnd);
int mid = bin_search(u);
vector<int> depth(n, -1);
depth[mid] = 0;
queue<int> q;
q.push(mid);
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto [to, i]: g[v]) {
if (depth[to] == -1) {
depth[to] = depth[v] + 1;
q.push(to);
}
}
}
sort(u.begin(), u.end(), [&depth](int i, int j) {
return depth[i] < depth[j];
});
solve(bin_search(u));
}
