#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
int M = U.size();
assert (M == N - 1);
vector<int> pa(N, -1), ei(N, -1), dep(N, 0);
vector<vector<pair<int, int>>> gr(N);
for (int i = 0; i < N-1; i++) {
gr[U[i]].push_back({V[i], i});
gr[V[i]].push_back({U[i], i});
}
auto build = [&](auto &&self, int v, int p) -> void {
for (auto [u, i] : gr[v]) if (u != p) {
pa[u] = v;
ei[u] = i;
dep[u] = dep[v] + 1;
self(self, u, v);
}
};
build(build, 0, -1);
vector<int> w(M, 0);
ll bfs = ask(w);
srand(260504);
set<int> vis, cur; for (int i = 0; i < N; i++) cur.insert(i);
auto f = [&](auto &&self, int v) -> void {
if (v) w[ei[v]] = 1;
vis.insert(v);
for (auto [u, i] : gr[v]) if (u != pa[v] && cur.count(u)) self(self, u);
};
set<int> z, oth;
int cnt = 0;
while (cnt < 80) {
vis.clear();
w.assign(M, 0);
int ch = rand() % N;
while (!cur.count(ch)) ch = rand() % N;
f(f, ch);
ll d = ask(w);
cnt++;
if (d == bfs)
for (auto x : vis) cur.erase(x);
else if (d * A == bfs * B) {
swap(vis, cur);
if (ch) cur.insert(pa[ch]);
}
else {
for (auto x : vis) cur.erase(x);
if (ch) vis.erase(pa[ch]);
int y = (d - bfs) / (B - A);
assert (1ll * y * (B - A) == d - bfs);
for (auto x : vis) if (dep[x] - dep[pa[ch]] == y) z.insert(x);
swap(oth, cur);
break;
}
}
assert (cnt < 80);
while (z.size() > 1) {
w.assign(M, 0);
set<int> ch;
for (auto x : z) if (rand() % 2) {
ch.insert(x);
w[ei[x]] = 1;
}
ll d = ask(w);
if (d == bfs) {for (auto x : ch) z.erase(x);}
else swap(z, ch);
}
assert (z.size() == 1);
int s = *z.begin();
z.clear();
auto re = [&](auto &&self, int v, int p, int d) -> void {
if (oth.count(v) && 1ll * d * A == bfs) z.insert(v);
for (auto [u, i] : gr[v]) if (u != p) {
ei[u] = i;
self(self, u, v, d + 1);
}
};
re(re, s, -1, 0);
while (z.size() > 1) {
w.assign(M, 0);
set<int> ch;
for (auto x : z) if (rand() % 2) {
ch.insert(x);
w[ei[x]] = 1;
}
ll d = ask(w);
if (d == bfs) {for (auto x : ch) z.erase(x);}
else swap(z, ch);
}
assert (z.size() == 1);
int t = *z.begin();
answer(s, t);
}
