#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 9e4 + 20;
vector<pair<int, int>> adj[maxN];
int sz[maxN];
int depth[maxN];
int par_id[maxN];
vector<pair<int, int>> group[maxN];
bool flag[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, long long mi) {
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;
}
long long res = ask(query);
for (auto p: left) {
query[p.second] = 0;
}
if (res == mi) {
cand = right;
}
else {
cand = left;
}
}
return cand[0].first;
}
void dfs2(int u, int p) {
sz[u] = 1;
for (auto e: adj[u]) {
int v = e.first;
if (v != p && !flag[v]) {
dfs2(v, u);
sz[u] += sz[v];
}
}
}
int cen(int r, int u, int p) {
for (auto e: adj[u]) {
int v = e.first;
if (v != p && !flag[v] && sz[v] * 2 > sz[r]) {
return cen(r, v, u);
}
}
return u;
}
void build(int u, int d) {
dfs2(u, -1);
u = cen(u, u, -1);
flag[u] = true;
for (auto e: adj[u]) {
int v = e.first;
int id = e.second;
if (!flag[v]) {
group[d].emplace_back(u, id);
build(v, d + 1);
}
}
}
vector<int> query;
void dfs3(int u, int p) {
for (auto e: adj[u]) {
int v = e.first;
int id = e.second;
if (v != p) {
query[id] = 1;
dfs3(v, u);
}
}
}
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;
build(0, 0);
int root = -1;
int sub = -1;
query.resize(M);
for (int d = 0; ; d++) {
for (auto p: group[d]) {
query[p.second] = 1;
}
long long res = ask(query);
for (auto p: group[d]) {
query[p.second] = 0;
}
if (res != 1LL * A * dist) {
vector<pair<int, int>> cand = group[d];
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;
}
long long res = ask(query);
for (auto p: left) {
query[p.second] = 0;
}
if (res == 1LL * A * dist) {
cand = right;
}
else {
cand = left;
}
}
root = cand[0].first;
int id = cand[0].second;
query[id] = 1;
sub = (U[id] == root ? V[id] : U[id]);
break;
}
}
dfs3(sub, root);
int d = (ask(query) - 1LL * A * dist) / (B - A);
int S = find_depth(root, d, 1LL * A * dist);
int T = find_depth(S, dist, 1LL * A * dist);
answer(S, T);
}
