#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;
vector < vector <pii> > g, gr;
vector <int> h, visited;
vector <pii> par;
void dfs(int u, int p, int id_w, int height) {
h[u] = height;
par[u] = {p, id_w};
for (auto to : gr[u])
if (to.fi != p)
dfs(to.fi, u, to.se, h[u] + 1);
}
void dfs_count(int u, int p) {
visited.pb(u);
for (auto to : gr[u])
if (to.fi != p)
dfs_count(to.fi, u);
}
bool cmp(pii x, pii y) {return x.se > y.se;}
int solve_from(int x, int dist, ll val, vector <int> vertical) {
visited.clear();
dfs_count(x, -1);
h.resize(n);
par.resize(n);
dfs(x, -1, -1, 0);
vector <pii> c(visited.size());
for (int i = 0; i < visited.size(); i++)
c[i] = {visited[i], h[visited[i]]};
sort(c.begin(), c.end(), cmp);
int L = 0, R = visited.size() - 1, M;
int idc = visited.size() - 1;
vector <int> w;
while (L <= R) {
w.assign(m, 0);
for (int to : vertical)
w[to] = 1;
M = (L + R) / 2;
for (int i = 0; i <= M; i++)
if (par[c[i].fi].fi != -1)
w[par[c[i].fi].se] = 1;
ll curval = ask(w);
if (curval > val) {
idc = min(idc, M);
R = M - 1;
} else
L = M + 1;
}
return c[idc].fi;
}
void bfs_tree(int x, int y) {
queue <int> q;
q.push(x);
q.push(y);
vector <bool> vis(n, false);
vis[x] = vis[y] = true;
while (!q.empty()) {
int cur = q.front();
q.pop();
for (auto to : g[cur]) {
if (vis[to.fi])
continue;
vis[to.fi] = true;
q.push(to.fi);
// cout << cur << " " << to.fi << endl;
gr[cur].pb(to);
gr[to.fi].pb({cur, to.se});
}
}
}
void find_pair(int n1, vector <int> U, vector <int> V, int A, int B) {
n = n1;
m = U.size();
g.resize(n);
gr.resize(n);
for (int i = 0; i < m; i++) {
g[U[i]].pb({V[i], i});
g[V[i]].pb({U[i], i});
}
vector <int> w(m, 0);
ll val = ask(w);
int dist = (val / (A * 1ll));
int L = 0, R = m - 1, M, x = m;
while (L <= R) {
w.assign(m, 0);
M = (L + R) / 2;
for (int i = 0; i <= M; i++)
w[i] = 1;
ll curval = ask(w);
if (curval > val) {
x = min(x, M);
R = M - 1;
} else
L = M + 1;
}
// cout << x << " " << U[x] << " " << V[x] << endl;
// cout << x << endl;
// return;
bfs_tree(U[x], V[x]);
vector <bool> vis(m, false);
vector <int> vertical;
for (int i = 0; i < n; i++)
for (auto to : gr[i])
vis[to.se] = true;
for (int i = 0; i < m; i++)
if (!vis[i] && i != x)
vertical.pb(i);
int s = solve_from(U[x], dist, val, vertical);
int t = solve_from(V[x], dist, val, vertical);
// cout << s << " " << t << endl;
answer(s, t);
}
