#include "highway.h"
#include <stdlib.h>
using namespace std;
typedef vector<int> vi;
const int N = 90000;
int *eh[N], eo[N];
void append(int i, int h) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
eh[i] = (int *) realloc(eh[i], o * 2 * sizeof *eh[i]);
eh[i][o] = h;
}
int ii[N - 1], jj[N - 1], hh[N - 1], m;
void dfs(int p, int i) {
int o;
for (o = eo[i]; o--; ) {
int h = eh[i][o], j = i ^ ii[h] ^ jj[h];
if (j != p) {
ii[h] = i, jj[h] = j;
dfs(i, j);
hh[m++] = h;
}
}
}
void find_pair(int n, vi ii_, vi jj_, int a, int b) {
vi ww(n - 1, 0);
int h, i, j, lower, upper;
long long d;
for (i = 0; i < n; i++)
eh[i] = (int *) malloc(2 * sizeof *eh[i]);
for (h = 0; h < n - 1; h++) {
i = ii[h] = ii_[h], j = jj[h] = jj_[h];
append(i, h), append(j, h);
}
d = ask(ww);
lower = -1, upper = n;
while (upper - lower > 1) {
i = (lower + upper) / 2;
for (h = 0; h < n - 1; h++)
ww[h] = ii[h] >= i || jj[h] >= i;
if (ask(ww) > d)
upper = i;
else
lower = i;
}
i = upper;
m = 0, dfs(-1, i);
lower = -1, upper = n - 1;
while (upper - lower > 1) {
int h_ = (lower + upper) / 2;
for (h = 0; h < n - 1; h++)
ww[hh[h]] = h <= h_;
if (ask(ww) > d)
upper = h_;
else
lower = h_;
}
i = jj[hh[upper]];
m = 0, dfs(-1, i);
lower = -1, upper = n - 1;
while (upper - lower > 1) {
int h_ = (lower + upper) / 2;
for (h = 0; h < n - 1; h++)
ww[hh[h]] = h <= h_;
if (ask(ww) > d)
upper = h_;
else
lower = h_;
}
answer(i, jj[hh[upper]]);
}
