#include "highway.h"
#include <stdlib.h>
#include <string.h>
using namespace std;
typedef vector<int> vi;
const int N = 90000, M = 130000;
int ii[M], jj[M];
int *eh[N], eo[N], 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[N - 1];
void bfs(int n, int s) {
static int dd[N], qu[N];
int i, head, cnt, m_;
for (i = 0; i < n; i++)
dd[i] = n;
head = cnt = 0, m_ = 0;
dd[s] = 0, qu[head + cnt++] = s;
while (cnt) {
int d, o;
i = qu[cnt--, head++], 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[m_++] = h, dd[j] = d, qu[head + cnt++] = j;
}
}
}
vi ww; int a, b; long long d;
int ask_(int k) {
static char marked[N];
int h;
long long d_;
memset(marked, 0, n * sizeof *marked);
for (h = k - 1; h < n - 1; h++)
marked[jj[hh[h]]] = 1;
for (h = 0; h < n - 1; h++)
ww[hh[h]] = !marked[ii[hh[h]]] && marked[jj[hh[h]]];
d_ = ask(ww);
if (d_ == d)
return 0;
else if (d_ == d + b - a)
return 1;
return 2;
}
int i, j;
void solve(int l, int r, int mask) {
int m = (l + r + 1) / 2, x;
if (mask == 0)
return;
if (l == r) {
if (mask == 1)
i = l == 0 ? ii[hh[0]] : jj[hh[l - 1]];
else
j = l == 0 ? ii[hh[0]] : jj[hh[l - 1]];
return;
}
x = ask_(m);
solve(l, m - 1, mask & ((x != 2) | (x == 0) << 1)), solve(m, r, mask & ((x == 2) | (x != 0) << 1));
}
void find_pair(int n_, vi ii_, vi jj_, int a_, int b_) {
int m = ii_.size(), h, lower, upper;
ww.resize(m);
n = n_, a = a_, b = b_;
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 = n;
while (upper - lower > 1) {
i = (lower + upper) / 2;
for (h = 0; h < m; h++)
ww[h] = ii[h] <= i || jj[h] <= i;
if (ask(ww) > d)
upper = i;
else
lower = i;
}
bfs(n, upper);
for (h = 0; h < m; h++)
ww[h] = 1;
solve(0, n - 1, 3);
answer(i, j);
}
