#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "highway.h"
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pll pair<long long, long long>
#define pii pair<int, int>
using namespace std;
//const int N = 2e5 + 10;
int n, m, max_height = 0, timer;
vector < vector <pii> > g;
vector < vector <int> > fixed_h;
vector <int> h, tin, tout;
vector <pii> par;
void dfs(int u, int p, int id_w, int height) {
tin[u] = ++timer;
max_height = max(max_height, height);
h[u] = height;
par[u] = {p, id_w};
for (auto to : g[u])
if (to.fi != p)
dfs(to.fi, u, to.se, h[u] + 1);
tout[u] = ++timer;
}
bool parent(int par, int u) {
return (tin[par] <= tin[u] && tout[par] >= tout[u]);
}
ll find_val() {
vector <int> w(m, 0);
return ask(w);
}
int find_height_lca(ll val) {
int L = 0, R = max_height, M, ans = 0;
vector <int> w;
while (L <= R) {
M = (L + R) / 2;
w.assign(m, 0);
for (int height = 0; height <= M; height++)
for (int to : fixed_h[height]) {
if (par[to].se >= 0)
w[par[to].se] = 1;
}
ll curval = ask(w);
if (curval > val) {
R = M - 1;
} else {
ans = max(ans, M);
L = M + 1;
}
}
return ans;
}
int get_answer(vector <int> candidates, ll val, bool flag=false) {
vector <int> L, R, w;
while (candidates.size() > 1) {
L.clear(); R.clear();
w.assign(m, 0);
int lim = candidates.size() / 2;
for (int i = 0; i < lim; i++) {
int u = candidates[i];
L.pb(u);
if (!flag) {
for (auto to : g[u])
if (par[u].fi != to.fi)
w[to.se] = 1;
} else {
if (par[u].se >= 0)
w[par[u].se] = 1;
}
}
for (int i = lim; i < candidates.size(); i++) {
R.pb(candidates[i]);
}
ll curval = ask(w);
if (curval > val)
candidates = L;
else
candidates = R;
}
return candidates[0];
}
vector <int> get_candidates(int u, int height) {
vector <int> ans = {};
for (int to : fixed_h[height])
if (parent(u, to))
ans.pb(to);
return ans;
}
int find_lca(int height, ll val) {
return get_answer(get_candidates(0, height), val);
}
int find_first_end(int lca, int dist, ll val) {
int L = h[lca] + (dist + 1) / 2, R = min(max_height, h[lca] + dist), M, ch = h[lca];
vector < vector <int> > fixed_h_cur;
fixed_h_cur.resize(max_height + 1);
for (int i = 0; i <= max_height; i++)
for (int to : fixed_h[i])
if (parent(lca, to))
fixed_h_cur[i].pb(to);
vector <int> w;
while (L <= R) {
M = (L + R) / 2;
w.assign(m, 0);
for (int height = M; height <= R; height++) {
for (int to : fixed_h_cur[height]) {
if (par[to].se >= 0)
w[par[to].se] = 1;
}
}
ll curval = ask(w);
if (curval > val) {
ch = max(ch, M);
L = M + 1;
} else
R = M - 1;
}
return get_answer(get_candidates(lca, ch), val, true);
}
void find_pair(int n1, vector <int> U, vector <int> V, int A, int B) {
n = n1;
m = U.size();
g.resize(n);
h.resize(n);
par.resize(n);
tin.resize(n);
tout.resize(n);
for (int i = 0; i < m; i++) {
g[U[i]].pb({V[i], i});
g[V[i]].pb({U[i], i});
}
timer = 0;
dfs(0, -1, -1, 0);
fixed_h.resize(max_height + 1);
for (int i = 0; i < n; i++)
fixed_h[h[i]].pb(i);
ll val = find_val();
int dist = val / (A * 1ll);
int height_lca = find_height_lca(val);
int lca = find_lca(height_lca, val);
int C = find_first_end(lca, dist, val);
int remain_dist = dist - (h[C] - h[lca]);
if (remain_dist == 0) {
answer(C, lca);
return;
}
vector <int> candidates = {};
for (auto cur : g[lca]) {
int to = cur.fi;
if (par[lca].fi == to || (parent(to, C)))
continue;
vector <int> tmp = get_candidates(to, h[lca] + remain_dist);
for (int x : tmp)
candidates.pb(x);
}
int T = get_answer(candidates, val, true);
answer(C, T);
}
