// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h>
using namespace std;
#include "highway.h"
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
#define INF 1000000005
#define LINF 1000000000000000005ll
#define MAXN 200005
int n, m;
vii adj[MAXN];
int a, b;
ll itoll;
vi w;
vi leaves;
ii p[MAXN];
int l[MAXN];
int pre[MAXN], pst[MAXN], ptr;
void dfs(int u) {
pre[u] = ptr++;
bool leaf = 1;
for (auto [v, i] : adj[u]) {
if (v == p[u].FI) continue;
leaf = 0;
p[v] = {u, i};
l[v] = l[u] + 1;
dfs(v);
}
if (leaf) {
leaves.pb(u);
}
pst[u] = ptr;
}
void findst(int u, int tl) {
if (l[u] == tl) {
leaves.pb(u);
return;
}
for (auto [v, i] : adj[u]) {
if (v == p[u].FI) continue;
findst(v, tl);
}
}
int bstaLeaves(int x = -1) {
int lo = 0, hi = leaves.size() - 1, mid;
while (lo < hi) {
w = vi(m, 0);
mid = lo + hi >> 1;
REP (i, lo, mid + 1) {
int u = leaves[i];
while (p[u].FI != -1) {
if (w[p[u].SE] == 1) {
break;
}
w[p[u].SE] = 1;
u = p[u].FI;
}
}
ll toll = ask(w);
int delta = (toll - itoll) / (b - a);
if ((x == -1 && toll != itoll) || delta == x) {
hi = mid;
} else {
lo = mid + 1;
}
}
return leaves[lo];
}
void find_pair(int N, vi U, vi V, int A, int B) {
n = N, m = U.size();
a = A, b = B;
REP (i, 0, m) {
adj[U[i]].pb({V[i], i});
adj[V[i]].pb({U[i], i});
}
p[0] = {-1, -1};
dfs(0);
w = vi(m, 0);
itoll = ask(w);
int dis = itoll / a;
int lo = 1, hi = 0, mid;
REP (i, 0, n) {
mxto(hi, l[i]);
}
while (lo < hi) {
mid = lo + hi >> 1;
w = vi(m, 0);
REP (i, 1, n) {
if (l[i] <= mid) {
w[p[i].SE] = 1;
}
}
ll toll = ask(w);
int x = (toll - itoll) / (b - a);
if (x == dis) {
hi = mid;
} else {
lo = mid + 1;
}
}
int sl = hi;
vi cand;
REP (i, 0, n) {
if (l[i] == sl) {
cand.pb(i);
}
}
assert(!cand.empty());
lo = 0, hi = cand.size() - 1;
while (lo < hi) {
mid = lo + hi >> 1;
w = vi(m, 0);
REP (i, 0, mid) {
w[p[cand[i]].SE] = 1;
}
ll toll = ask(w);
if (toll != itoll) {
assert(toll == itoll + b - a);
hi = mid;
} else {
lo = mid + 1;
}
}
int s = cand[hi];
int u = s;
w = vi(m, 0);
while (p[u].FI != -1) {
w[p[u].SE] = 1;
u = p[u].FI;
}
ll toll = ask(w);
int ldis = (toll - itoll) / (b - a);
int rdis = dis - ldis;
int lca = s, nxt = s;;
REP (i, 0, ldis) {
nxt = lca;
lca = p[lca].FI;
}
leaves.clear();
for (auto [v, i] : adj[lca]) {
if (v == p[lca].FI || v == nxt) continue;
findst(v, l[lca] + rdis);
}
int t = -1;
if (leaves.empty()) {
t = lca;
} else {
t = bstaLeaves(rdis);
}
answer(s, t);
}
/*
void find_pair(int N, vi U, vi V, int A, int B) {
n = N, m = U.size();
a = A, b = B;
REP (i, 0, m) {
adj[U[i]].pb({V[i], i});
adj[V[i]].pb({U[i], i});
}
p[0] = {-1, -1};
dfs(0);
w = vi(m, 0);
itoll = ask(w);
int dis = itoll / a;
int s = bstaLeaves();
int lo = 0, hi = l[s] - 1, mid;
while (lo < hi) {
mid = lo + hi + 1 >> 1;
int u = s;
while (l[u] > mid) {
u = p[u].FI;
}
vi w(m, 0);
while (p[u].FI != -1) {
w[p[u].SE] = 1;
u = p[u].FI;
}
ll toll = ask(w);
if (toll == itoll) {
lo = mid;
} else {
hi = mid - 1;
}
}
int lca = s;
int nxt = s;
while (l[lca] > lo) {
nxt = lca;
lca = p[lca].FI;
}
w = vi(m, 0);
REP (i, 0, n) {
if (pre[nxt] <= pre[i] && pre[i] < pst[nxt]) {
w[p[i].SE] = 1;
}
}
ll toll = ask(w);
int ldis = (toll - itoll) / (b - a);
int rdis = dis - ldis;
cerr << lca << ' ' << ldis << ' ' << rdis << '\n';
leaves.clear();
for (auto [v, i] : adj[lca]) {
if (v == p[lca].FI || v == nxt) continue;
findst(v, l[lca] + rdis);
}
int t = -1;
if (leaves.empty()) {
t = lca;
} else {
t = bstaLeaves(rdis);
}
leaves.clear();
findst(nxt, l[lca] + ldis);
assert(!leaves.empty());
s = bstaLeaves(ldis);
cerr << s << ' ' << t << '\n';
answer(s, t);
}
*/
