#include "highway.h"
#include <stdlib.h>
using namespace std;
typedef vector<int> vi;
const int N = 90000, M = 130000;
int ii[M], jj[M];
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 hh[2][N - 1], mm[2];
void bfs(int n, int h) {
static int cc[N], dd[N], qu[N];
int i, head, cnt;
for (i = 0; i < n; i++)
dd[i] = n;
head = cnt = 0;
cc[ii[h]] = 0, dd[ii[h]] = 0, qu[head + cnt++] = ii[h];
cc[jj[h]] = 1, dd[jj[h]] = 0, qu[head + cnt++] = jj[h];
while (cnt) {
int c, d, o;
i = qu[cnt--, head++], c = cc[i], d = dd[i] + 1;
for (o = eo[i]; o--; ) {
int h = eh[i][o], j = i ^ ii[h] ^ jj[h];
if (dd[j] > d) {
ii[h] = i, jj[h] = j, hh[c][mm[c]++] = h;
cc[j] = c, dd[j] = d, qu[head + cnt++] = j;
}
}
}
}
void find_pair(int n, vi ii_, vi jj_, int a, int b) {
int m = ii_.size(), h, h_, h1, i, j, c, lower, upper;
vi ww(m, 0);
long long d;
for (i = 0; i < n; i++)
eh[i] = (int *) malloc(2 * sizeof *eh[i]);
for (h = 0; h < m; h++) {
i = ii[h] = ii_[h], j = jj[h] = jj_[h];
append(i, h), append(j, h);
}
d = ask(ww);
lower = -1, upper = m;
while (upper - lower > 1) {
h_ = (lower + upper) / 2;
for (h = 0; h < m; h++)
ww[h] = h <= h_;
if (ask(ww) > d)
upper = h_;
else
lower = h_;
}
bfs(n, h1 = upper);
for (c = 0; c < 2; c++) {
for (h = 0; h < m; h++)
ww[h] = 1;
lower = -1, upper = mm[c];
while (upper - lower > 1) {
h_ = (lower + upper) / 2;
for (h = 0; h < mm[c]; h++)
ww[hh[c][h]] = h >= h_;
for (h = 0; h < mm[c ^ 1]; h++)
ww[hh[c ^ 1][h]] = 0;
ww[h1] = 0;
if (ask(ww) > d)
lower = h_;
else
upper = h_;
}
if (lower != -1) {
if (c == 0)
ii[h1] = jj[hh[c][lower]];
else
jj[h1] = jj[hh[c][lower]];
}
}
answer(ii[h1], jj[h1]);
}
