#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 9e4 + 20;
vector<pair<int, int>> adj[maxN];
int depth[maxN];
int par_id[maxN];
int N, M, A, B;
void dfs1(int u, int p) {
for (auto e: adj[u]) {
int v = e.first;
int id = e.second;
if (v != p) {
depth[v] = depth[u] + 1;
par_id[v] = id;
dfs1(v, u);
}
}
}
int find_depth(int root, int d) {
if (d == 0) {
return root;
}
depth[root] = 0;
dfs1(root, -1);
vector<int> query(M, 0);
vector<pair<int, int>> cand;
for (int i = 0; i < N; i++) {
if (depth[i] == d) {
cand.emplace_back(i, par_id[i]);
}
}
while ((int)cand.size() > 1) {
int sz = cand.size();
vector<pair<int, int>> left(cand.begin(), cand.begin() + sz / 2);
vector<pair<int, int>> right(cand.begin() + sz / 2, cand.end());
for (auto p: left) {
query[p.second] = 1;
}
int res = ask(query);
for (auto p: left) {
query[p.second] = 0;
}
if (res == 1LL * A * d) {
cand = right;
}
else {
cand = left;
}
}
return cand[0].first;
}
void find_pair(int _N, vector<int> U, vector<int> V, int _A, int _B) {
N = _N;
M = U.size();
A = _A;
B = _B;
for (int i = 0; i < M; i++) {
adj[U[i]].emplace_back(V[i], i);
adj[V[i]].emplace_back(U[i], i);
}
int dist = ask(vector<int>(M, 0)) / A;
int S = find_depth(0, 0);
int T = find_depth(S, dist);
answer(S, T);
}
