#include "highway.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
vector<vector<ii> > adj(N);
int M = U.size();
for (int i = 0; i < M; i++) {
adj[U[i]].emplace_back(V[i], i);
adj[V[i]].emplace_back(U[i], i);
}
int64_t all_b = ask(vector<int>(M, 1));
int64_t all_a = all_b / B * A;
int lo = 0, hi = M;
while (hi - lo > 1) {
int mid = (lo + hi) >> 1;
vector<int> orz(M, 0);
for (int i = 0; i <= mid; i++) orz[i] = 1;
if (ask(orz) == all_b) hi = mid;
else lo = mid;
}
int X = U[lo], Y = V[lo];
vector<int> depthX(N, 0), depthY(N, 0), peX(N, -1), peY(N, -1);
function<void(int, int)> pfsX = [&](int u, int dad) {
for (auto [v, idx] : adj[u])
if (v != dad) {
depthX[v] = depthX[u] + 1;
peX[v] = idx;
pfsX(v, u);
}
};
function<void(int, int)> pfsY = [&](int u, int dad) {
for (auto [v, idx] : adj[u])
if (v != dad) {
depthY[v] = depthY[u] + 1;
peY[v] = idx;
pfsY(v, u);
}
};
pfsX(X, -1);
pfsY(Y, -1);
vector<int> lisX(1, X), lisY(1, Y);
for (int i = 0; i < N; i++)
if (i != X && i != Y) {
if (depthX[i] < depthY[i]) lisX.emplace_back(i);
else lisY.emplace_back(i);
}
int S = X, T = Y;
if (1) {
sort(lisX.begin(), lisX.end(), [&](int x, int y) {return depthX[x] > depthX[y];});
int lo = -1, hi = lisX.size() - 1;
while (hi - lo > 1) {
int mid = (lo + hi) >> 1;
vector<int> orz(M, 0);
for (int i = 0; i <= mid; i++) orz[peX[lisX[i]]] = 1;
if (ask(orz) != all_a) hi = mid;
else lo = mid;
}
S = lisX[hi];
}
if (1) {
sort(lisY.begin(), lisY.end(), [&](int x, int y) {return depthY[x] > depthY[y];});
int lo = -1, hi = lisY.size() - 1;
while (hi - lo > 1) {
int mid = (lo + hi) >> 1;
vector<int> orz(M, 0);
for (int i = 0; i <= mid; i++) orz[peY[lisY[i]]] = 1;
if (ask(orz) != all_a) hi = mid;
else lo = mid;
}
T = lisY[hi];
}
answer(S, T);
}
/*
4 3
1 3 1 3
1 2
2 0
0 3
*/
