#include "highway.h"
#include <bits/stdc++.h>
#define ll long long
#define point pair<int, int>
#define pb push_back
#define show(x) cerr << (#x) << " = " << x << '\n'
using namespace std;
const int N = 1 << 18;
int n, a, b, len;
vector<point> g[N];
vector<point> e;
#define int ll
int norm(int s) {
// show(s);
return (s - a * len) / (b - a);
}
int Q = 0;
int query(vector<signed> v) {
++Q;
if (Q >= 60)
while(true) {}
int res = norm(ask(v));
return res;
}
vector<int> lst;
void dfs(int v, int pr, int dist, int target) {
// show(v);
assert(v < N && v >= 0);
for (auto [to, id] : g[v]) {
if (to == pr)
continue;
// show(v), show(to);
if (e[id].first != v)
swap(e[id].first, e[id].second);
if (target == -1 || target == dist + 1) {
lst.pb(id);
}
dfs(to, v, dist + 1, target);
}
}
int solve_rooted(int root, int pr) {
// show(root), show(pr);
dfs(root, pr, 0, -1);
assert(!lst.empty());
// show(lst.size());
vector<signed> f(n - 1);
for (int x : lst)
f[x] = true;
int p = query(f);
// show(p);
if (p == 0)
return root;
lst.clear();
dfs(root, pr, 0, p);
assert(!lst.empty());
int l = 0, r = lst.size() - 1;
while (l < r) {
int mid = (l + r) >> 1;
vector<signed> v(n - 1);
for (int i = l; i <= mid; ++i)
v[lst[i]] = true;
if (query(v))
r = mid;
else
l = mid + 1;
}
// show(l), show(r);
return e[lst[l]].second;
}
void find_pair(signed _N, vector<signed> U, vector<signed> V, signed A, signed B) {
n = _N, a = A, b = B;
assert(n < N);
for (int i = 0; i + 1 < n; ++i)
g[U[i]].pb({V[i], i}), g[V[i]].pb({U[i], i}), e.pb({U[i], V[i]});
len = ask(vector<signed>(n - 1)) / a;
int ans = solve_rooted(0, -1);
// show(ans);
assert(ans > 0);
answer(0, ans); return;
int l = 0, r = n - 2;
int tt = 0;
while (l < r) {
int mid = (l + r) >> 1;
vector<signed> v(n - 1);
fill(v.begin() + l, v.begin() + mid + 1, 1);
// for (int x : v)
// cerr << x;
// cerr << '\n';
if (query(v))
r = mid;
else
l = mid + 1;
}
auto [x, y] = e[l];
// show(x), show(y);
vector<signed> check(n - 1);
check[l] = true;
assert(query(check));
int res_x = solve_rooted(x, y);
int res_y = solve_rooted(y, x);
answer(res_x, res_y);
}
//6 5 1 2 0 5
//0 1
//0 4
//1 2
//1 3
//4 5
