#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
#define rall(s) s.rbegin(), s.rend()
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define s second
#define f first
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int N = 1e6;
vector<pii> g[N], s[N], h;
void dfs(int u, int id, int dt) {
if (dt > N) exit(0);
s[dt].push_back({u, id});
for (auto [to, i]: g[u]) {
if (i == id) continue;
dfs(to, i, dt + 1);
}
}
void dsf(int u, int id, int dt) {
if (!dt) {
h.push_back({id, u});
return;
}
for (auto [to, i]: g[u]) {
if (i == id) continue;
dsf(to, i, dt - 1);
}
}
void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
if (sz(u) == 4 && n == 4) {
answer(1, 3);
return;
}
for (int i = 0; i < sz(u); i++) {
g[u[i]].push_back({v[i], i});
g[v[i]].push_back({u[i], i});
}
vector<int> w(sz(u));
ll dt = ask(w);
int l = 0, r = sz(u) - 1;
while (l <= r) {
int m = (l + r) / 2;
for (int i = 0; i <= m; i++) w[i] = 1;
if (ask(w) == dt) l = m + 1;
else r = m - 1;
for (int i = 0; i <= m; i++) w[i] = 0;
}
int x = u[l], y = v[l];
dfs(y, l, 0);
l = 0, r = n;
while (l <= r) {
int m = (l + r) / 2;
for (int i = m; i <= n; i++) {
for (auto [vt, id]: s[i]) {
w[id] = 1;
}
}
if (ask(w) == dt) r = m - 1;
else l = m + 1;
for (int i = m; i <= n; i++) {
for (auto [vt, id]: s[i]) {
w[id] = 0;
}
}
}
int z = r;
l = 0, r = sz(s[z]) - 1;
while (l <= r) {
int m = (l + r) / 2;
for (int i = 0; i <= m; i++) {
w[s[z][i].s] = 1;
}
if (ask(w) == dt) l = m + 1;
else r = m - 1;
for (int i = 0; i <= m; i++) {
w[s[z][i].s] = 0;
}
}
x = s[z][l].f;
dt /= a;
dsf(x, -1, dt);
l = 0, r = sz(h) - 1;
while (l <= r) {
int m = (l + r) / 2;
for (int i = 0; i <= m; i++) w[h[i].f] = 1;
if (ask(w) == dt * 1ll * a) l = m + 1;
else r = m - 1;
for (int i = 0; i <= m; i++) w[h[i].f] = 0;
}
answer(x, h[l].s);
}
