#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> nodes[2];
function<void(int, int, bool)> dfs = [&](int i, int p, bool c) {
nodes[c].push_back(i);
for (auto [j, _] : adj[i])
if (j != p)
dfs(j, i, !c);
};
dfs(0, 0, 0);
vt<int> poss;
if (C / A & 1) {
poss = nodes[0];
goto jail;
}
FOR(_, 0, 1) {
FOR(b, 0, 31 - __builtin_clz(size(nodes[_]))) {
vt<int> v(M);
FOR(ii, 0, size(nodes[0])-1)
if (ii & 1 << b) {
int i = nodes[0][ii];
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();
}
if (size(poss))
break;
}
jail:;
#ifdef DEBUG
cout << "possible:";
for (int i : poss)
cout << ' ' << i;
cout << '\n';
#endif
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 = poss[lo];
poss.clear();
int par[N];
function<void(int, int, int)> dfs2 = [&](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;
dfs2(j, i, d + 1);
}
};
dfs2(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]);
}
