#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define mt make_tuple
using ll = long long;
using ii = pair<int, int>;
int ed;
vector<int> ndep;
vector<vector<int> > U_edges, V_edges;
vector<vector<ii> > adj;
void dfs(int u, vector<vector<int> > &edges, int dep = 0, int e = -1) {
ndep[u] = dep;
for (auto [v, idx] : adj[u]) if (v != e && idx != ed) {
edges[dep].pb(idx);
dfs(v, edges, dep + 1, u);
}
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
ndep.resize(N);
adj.resize(N);
int M = (int)U.size();
vector<int> cur;
for (int i = 0; i < M; i++) {
adj[U[i]].eb(V[i], i);
adj[V[i]].eb(U[i], i);
cur.pb(i);
}
ll original = ask(vector<int>(M, 0));
while ((int)cur.size() > 1) {
vector<int> w(M, 0);
for (int i = 0; i < (int)cur.size() / 2; i++) {
w[cur[i]] = 1;
}
if (ask(w) > original) {
int new_sz = (int)cur.size() / 2;
while ((int)cur.size() != new_sz) cur.pop_back();
} else {
int new_sz = ((int)cur.size() + 1) / 2;
reverse(cur.begin(), cur.end());
while ((int)cur.size() != new_sz) cur.pop_back();
reverse(cur.begin(), cur.end());
}
}
ed = cur[0];
U_edges.resize(N);
V_edges.resize(N);
dfs(U[ed], U_edges);
dfs(V[ed], V_edges);
vector<int> w(M, 0);
for (auto edges_by_dep : U_edges) {
for (auto edge : edges_by_dep) {
w[edge] = 1;
}
}
ll tmp = ask(w);
int U_len = (tmp - original) / (B - A);
int V_len = original / A - U_len - 1;
int S, T;
for (auto [len, edges, R, W] : {mt(U_len, U_edges, &S, U), mt(V_len, V_edges, &T, V)}) {
if (len) {
vector<int> cur = edges[len - 1];
while ((int)cur.size() > 1) {
vector<int> w(M, 0);
for (int i = 0; i < (int)cur.size() / 2; i++) {
w[cur[i]] = 1;
}
if (ask(w) > original) {
int new_sz = (int)cur.size() / 2;
while ((int)cur.size() != new_sz) cur.pop_back();
} else {
int new_sz = ((int)cur.size() + 1) / 2;
reverse(cur.begin(), cur.end());
while ((int)cur.size() != new_sz) cur.pop_back();
reverse(cur.begin(), cur.end());
}
}
*R = (ndep[U[cur[0]]] > ndep[V[cur[0]]] ? U[cur[0]] : V[cur[0]]);
} else {
*R = W[ed];
}
}
answer(S, T);
}
