#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)
void find_pair(int N, vt<int> U, vt<int> V, int A, int B) {
const int M = size(U);
vt<ari2> adj[N];
FOR(i, 0, M-1) {
adj[U[i]].push_back({V[i], i});
adj[V[i]].push_back({U[i], i});
}
ll C = ask(vt<int>(M));
vt<int> poss;
FOR(b, 0, 31 - __builtin_clz(N)) {
vt<int> v(M);
FOR(i, 0, N-1)
if (i & 1 << b) {
poss.push_back(i);
for (auto [_, j] : adj[i])
v[j] = 1;
}
ll X = ask(v);
int a = (X - C) / (B - A);
if (a & 1)
break;
poss.clear();
}
int lo = 0, hi = size(poss) - 1;
while (lo < hi) {
int mid = lo + hi >> 1;
vt<int> v(M);
FOR(ii, 0, mid) {
int i = poss[ii];
for (auto [_, j] : adj[i])
v[j] = 1;
}
ll X = ask(v);
int a = (X - C) / (B - A);
if (a & 1)
hi = mid;
else
lo = mid + 1;
}
int ep = 0;
poss.clear();
int par[N];
function<void(int, int, int)> dfs = [&](int i, int p, int d) {
if (d == C / A) {
poss.push_back(i);
return;
}
for (auto [j, ei] : adj[i])
if (j != p) {
par[j] = ei;
dfs(j, i, d + 1);
}
};
dfs(ep, ep, 0);
lo = 0, hi = size(poss) - 1;
while (lo < hi) {
int mid = lo + hi >> 1;
vt<int> v(M);
FOR(ii, 0, mid) {
int i = poss[ii];
v[par[i]] = 1;
}
if (ask(v) != C)
hi = mid;
else
lo = mid + 1;
}
answer(ep, poss[lo]);
}
