#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <vector>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <functional>
#include <queue>
#include <deque>
#include <stack>
#include <cassert>
#include <iomanip>
#include <cmath>
#include <bitset>
using namespace std;
#include "highway.h"
using int64 = long long;
// cache
map<pair<int, int>, int> eidx;
int eget(int u, int v) {
if (u > v) swap(u, v);
return eidx[{u, v}];
}
void eset(int u, int v, int idx) {
if (u > v) swap(u, v);
eidx[{u, v}] = idx;
}
//
vector<vector<int>> adj;
vector<int> dist;
vector<int> par;
void dfs(int n, int p) {
for (int v : adj[n]) {
if (v != p) {
dist[v] = dist[n] + 1;
par[v] = n;
dfs(v, n);
}
}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
int M = U.size();
int S = -1;
int T = -1;
// Step 0. Find min dist, 1 query
vector<int> w(M);
int64 D = ask(w) / A;
// Step 1. Find edge on min - path, 18 queries worst-case (!)
int l = 0, r = M - 1, sol = -1;
while (l <= r) {
int m = (l + r) >> 1;
w.assign(M, 0);
for (int i = 0; i <= m; i++)
w[i] = 1;
int64 cur = ask(w);
if (cur > D * A) {
sol = m;
r = m - 1;
} else {
l = m + 1;
}
}
assert(sol != -1);
cerr << "Critical edge: " << U[sol] << " -> " << V[sol] << "\n";
// 51 points, tree
adj.assign(N, vector<int>{});
for (int i = 0; i < M; i++) {
adj[ U[i] ].push_back( V[i] );
adj[ V[i] ].push_back( U[i] );
eset(U[i], V[i], i);
}
auto solve_half_tree = [&] (int x, int y, int & R) {
R = -1;
cerr << "solve_half_tree, start: " << x << " par: " << y << "\n";
dist.assign(N, 0);
par.assign(N, -1);
dfs(x, y);
w.assign(M, 0);
for (int i = 0; i < N; i++) {
if (par[i] != -1) {
w[eget(i, par[i])] = 1;
}
}
int64 depth = ask(w);
bool ok = false;
for (int i = 0; i < N; i++) {
if ((int64)i * B + (int64)(D - i) * A == depth) {
depth = i;
ok = true;
break;
}
}
assert(ok);
cerr << "depth: " << depth << "\n";
if (!depth) {
R = x;
} else {
vector<int> cand;
for (int i = 0; i < N; i++) {
if (par[i] != -1 && dist[i] == depth) {
cand.push_back(i);
}
}
assert(cand.size());
function<int(int, int)> rec = [&] (int l, int r) {
if (l == r) {
return cand[l];
}
int m = (l + r) >> 1;
vector<int> w(M);
for (int i = l; i <= m; i++) {
w[eget(cand[i], par[cand[i]])] = 1;
}
bool ok = ask(w) > D * A;
if (ok) {
return rec(l, m);
} else {
return rec(m + 1, r);
}
};
R = rec(0, cand.size() - 1);
};
};
solve_half_tree(U[sol], V[sol], S);
solve_half_tree(V[sol], U[sol], T);
cerr << S << " " << T << "\n";
assert(S != T);
answer(S, T);
}
