/* https://www.ioi-jp.org/camp/2017/2017-sp-tasks/2017-sp-d3-natural_park-review.pdf */
#include "park.h"
#include <stdlib.h>
#include <string.h>
const int N = 1400;
int *ej[N], eo[N], n;
void append(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;
}
int ask(int i, int j, int *used) {
int tmp;
if (i > j)
tmp = i, i = j, j = tmp;
used[i] = used[j] = 1;
return Ask(i, j, used);
}
void answer(int i, int j) {
int tmp;
if (i > j)
tmp = i, i = j, j = tmp;
Answer(i, j);
append(i, j), append(j, i);
}
int query(int *ii, int k, int j, int type) {
static int used[N];
for (int i = 0; i < n; i++)
used[i] = type ^ 1;
for (int h = 0; h < k; h++)
used[ii[h]] = type;
return ask(type == 0 ? 0 : ii[0], j, used);
}
char visited[N]; int qu[N], cnt;
void dfs(int i) {
if (visited[i])
return;
visited[i] = 1, qu[cnt++] = i;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
dfs(j);
}
}
void search(int *ii, int k, int j) {
while (k > 0) {
for (int i = 0; i < n; i++)
visited[i] = 1;
for (int h = 0; h < k; h++)
visited[ii[h]] = 0;
cnt = 0, dfs(ii[0]);
if (query(qu, cnt, j, 1)) {
int lower = -1, upper = cnt - 1;
while (upper - lower > 1) {
int h = (lower + upper) / 2;
if (query(qu, h + 1, j, 1))
upper = h;
else
lower = h;
}
int i = qu[upper];
answer(i, j);
for (int h = 0; h < k; h++)
if (ii[h] == i) {
while (h + 1 < k)
ii[h] = ii[h + 1], h++;
ii[h] = i;
break;
}
k--;
} else {
int tmp;
for (int h = 0, h_ = 0; h < k; h++)
if (!visited[ii[h]])
tmp = ii[h_], ii[h_] = ii[h], ii[h] = tmp, h_++;
k -= cnt;
}
}
}
void Detect(int t_, int n_) {
static int ii[N];
n = n_;
for (int j = 0; j < n; j++) {
int lower = 0, upper = j;
while (upper - lower > 1) {
int h = (lower + upper) / 2;
if (query(ii + h, j - h, j, 0))
upper = h;
else
lower = h;
}
for (int h = j; h > upper; h--)
ii[h] = ii[h - 1];
ii[upper] = j;
}
for (int i = 0; i < n; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
for (int h = 1; h < n; h++)
search(ii, h, ii[h]);
for (int i = 0; i < n; i++)
free(ej[i]);
}
