#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_lower_level(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 = M; height <= R; height++)
for (int to : fixed_h[height]) {
if (par[to].se >= 0)
w[par[to].se] = 1;
}
ll curval = ask(w);
if (curval > val) {
L = M + 1;
ans = max(ans, M);
} else {
R = M - 1;
}
}
return ans;
}
int get_answer(vector <int> candidates, ll val) {
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 (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];
}
int solve_from(int C, int dist, ll val) {
max_height = 0; timer = 0;
dfs(C, -1, -1, 0);
fixed_h.resize(max_height + 1);
for (int i = 0; i <= max_height; i++)
fixed_h[i].clear();
for (int i = 0; i < n; i++)
fixed_h[h[i]].pb(i);
return get_answer(fixed_h[dist], val);
}
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 lower_level = find_lower_level(val);
int C = get_answer(fixed_h[lower_level], val);
int T = solve_from(C, dist, val);
// cout << C << " " << T << endl;
answer(C, T);
}
