/* https://codeforces.com/blog/entry/91608 */
#include "game.h"
#include <stdlib.h>
const int N = 300000;
int *ej[N], eo[N], *fi[N], fo[N], ll[N], rr[N], n, k;
void append(int **ej, int *eo, int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
void init(int n_, int k_) {
n = n_, k = k_;
for (int i = 0; i < n; i++) {
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
fi[i] = (int *) malloc(2 * sizeof *fi[i]);
}
for (int i = 0; i < n; i++)
if (i < k)
ll[i] = rr[i] = i;
else
ll[i] = -1, rr[i] = k;
}
int add(int i, int j) {
int m, o;
if (rr[i] < ll[j])
return 0;
if (rr[j] < ll[i])
return 1;
if (ll[i] == ll[j] && rr[i] == rr[j])
return 0;
if (ll[i] <= ll[j] && rr[j] <= rr[i]) {
m = ll[i] + (rr[i] - ll[i]) / 2;
if (rr[j] > m)
return 0;
rr[i] = m;
if (i >= k && ll[i] == rr[i])
return 1;
for (o = eo[i]; o--; ) {
int v = ej[i][o];
if (add(i, v))
return 1;
}
for (o = fo[i]; o--; ) {
int u = fi[i][o];
if (add(u, i))
return 1;
}
return add(i, j);
} else {
m = ll[j] + (rr[j] - ll[j]) / 2;
if (ll[i] <= m)
return 0;
ll[j] = m + 1;
if (j >= k && ll[j] == rr[j])
return 1;
for (o = eo[j]; o--; ) {
int v = ej[j][o];
if (add(j, v))
return 1;
}
for (o = fo[j]; o--; ) {
int u = fi[j][o];
if (add(u, j))
return 1;
}
return add(i, j);
}
}
int add_teleporter(int i, int j) {
if (i == j)
return i < k;
if (add(i, j))
return 1;
append(ej, eo, i, j), append(fi, fo, j, i);
return 0;
}
