#include "bits/extc++.h"
using namespace std;
template <typename T>
void dbgh(const T& t) {
cerr << t << endl;
}
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t << " | ";
dbgh(u...);
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr \
if (false) \
cerr
#endif
using ll = long long;
#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())
ll ask(const vector<int>& w);
void answer(int s, int t);
const int maxn = 1e5 + 5;
int n, m;
long qa, qb, def;
vector<pair<int, int>> graph[maxn];
int bsearch(const vector<int>& arr) {
if (sz(arr) == 1) {
return arr[0];
}
int mid = sz(arr) / 2;
vector<int> l(arr.begin(), arr.begin() + mid),
r(arr.begin() + mid, arr.end());
vector<int> tmp(m);
for (auto& a : l) {
tmp[a] = true;
}
if (ask(tmp) > def) {
return bsearch(l);
} else {
return bsearch(r);
}
}
vector<array<int, 3>> cvals;
void dfs1(int u, int p = -1, int d = 0) {
for (auto& [v, i] : graph[u]) {
if (v != p) {
cvals.push_back({i, v, d + 1});
dfs1(v, u, d + 1);
}
}
}
int solve(int u) {
cvals.clear();
dfs1(u);
vector<int> tmp(m);
for (auto& a : cvals) {
tmp[a[0]] = true;
}
long cx = ask(tmp);
int depth = (cx - def) / (qb - qa);
if (!depth) {
return u;
}
tmp.clear();
for (auto& [i, _, d] : cvals) {
if (d == depth) {
tmp.push_back(i);
}
}
int cans = bsearch(tmp);
for (auto& [i, v, _] : cvals) {
if (i == cans) {
return v;
}
}
assert(false);
}
void find_pair(int _n, vector<int> us, vector<int> vs, int _qa, int _qb) {
n = _n;
m = sz(us);
qa = _qa;
qb = _qb;
for (int i = 0; i < m; i++) {
graph[us[i]].emplace_back(vs[i], i);
graph[vs[i]].emplace_back(us[i], i);
}
def = ask(vector<int>(m));
vector<int> tmp(m);
iota(begin(tmp), end(tmp), 0);
int ind = bsearch(tmp);
auto erase = [&](int u) -> void {
vector<pair<int, int>> tmp;
for (auto& [v, a] : graph[u]) {
if (a != ind) {
tmp.emplace_back(v, a);
}
}
swap(tmp, graph[u]);
};
erase(us[ind]);
erase(vs[ind]);
dbg(us[ind], vs[ind]);
answer(solve(us[ind]), solve(vs[ind]));
}
