#include "highway.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
const int MAX_N = 1e5;
int n, m;
int a, b;
vii graph[MAX_N];
pii par[MAX_N];
vi dist[MAX_N];
ll original;
bitset<MAX_N> visited;
void Dfs(int node, int parent, int d) {
dist[d].push_back(node);
visited[node] = true;
par[node].x = parent;
for (auto [neighbor, ind] : graph[node]) {
if (neighbor == parent) par[node].y = ind;
else Dfs(neighbor, node, d + 1);
}
}
int Solve(int u, int v) {
for (int i = 0; i < n; i++) dist[i].clear();
visited.reset();
Dfs(u, v, 0);
vi query(m);
for (int i = 0; i < n; i++) {
if (visited[i]) query[par[i].y] = 1;
}
query[par[u].y] = 0;
ll toll = ask(query);
int d = (toll - original) / (b - a);
fill(all(query), 0);
vi &options = dist[d];
int begin = 0, end = options.size(), mid;
while (begin < end) {
mid = (begin + end) >> 1;
for (int i = begin; i <= mid; i++) {
query[par[options[i]].y] = 1;
}
if (ask(query) > original) end = mid;
else begin = mid + 1;
for (int i = begin; i <= mid; i++) {
query[par[options[i]].y] = 0;
}
}
return options[end];
}
void find_pair(int N, vi U, vi V, int A, int B) {
m = U.size(), n = N;
a = A, b = B;
for (int i = 0; i < m; i++) {
graph[U[i]].push_back({V[i], i});
graph[V[i]].push_back({U[i], i});
}
original = ask(vi(m));
int begin = 0, end = m, mid;
while (begin < end) {
mid = (begin + end) >> 1;
vi v(m);
fill(v.begin() + begin, v.begin() + mid + 1, 1);
if (ask(v) > original) end = mid;
else begin = mid + 1;
}
answer(Solve(U[end], V[end]), Solve(V[end], U[end]));
}
