#include "icc.h"
#include <string.h>
#define N 100
int ds[N];
int find(int i) {
return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}
void join(int i, int j) {
i = find(i);
j = find(j);
if (i == j)
return;
if (ds[i] > ds[j])
ds[i] = j;
else {
if (ds[i] == ds[j])
ds[i]--;
ds[j] = i;
}
}
void run(int n) {
static int cc[N], ii1[N], ii2[N];
int h;
memset(ds, -1, n * sizeof *ds);
for (h = 0; h < n - 1; h++) {
int n1, n2, i, j, l, l_, c, c1, c2, lower, upper;
for (i = 0, c = 0; i < n; i++)
if (ds[i] < 0)
cc[i] = c++;
for (i = 0; i < n; i++)
cc[i] = cc[find(i)];
c2 = 0, l_ = -1;
for (l = 0; (1 << l) < c; l++) {
n1 = 0, n2 = 0;
for (i = 0; i < n; i++)
if ((cc[i] & 1 << l) == 0)
ii1[n1++] = i + 1;
else
ii2[n2++] = i + 1;
if (n1 != 0 && n2 != 0 && query(n1, n2, ii1, ii2))
c2 |= 1 << l, l_ = l;
}
c1 = 0;
for (l = 0; (1 << l) < c; l++) {
if (l == l_)
continue;
n1 = 0, n2 = 0;
for (i = 0; i < n; i++)
if ((cc[i] & ((1 << l) | (1 << l_))) == 0)
ii1[n1++] = i + 1;
else
ii2[n2++] = i + 1;
if (n1 == 0 || n2 == 0 || !query(n1, n2, ii1, ii2))
c1 |= 1 << l;
}
c2 ^= c1;
n1 = 0, n2 = 0;
for (i = 0; i < n; i++)
if (cc[i] == c1)
ii1[n1++] = i + 1;
else if (cc[i] == c2)
ii2[n2++] = i + 1;
lower = 0, upper = n1;
while (upper - lower > 1) {
int g = (lower + upper) / 2;
if (query(g - lower, n2, ii1 + lower, ii2))
upper = g;
else
lower = g;
}
i = ii1[lower] - 1;
lower = 0, upper = n2;
while (upper - lower > 1) {
int g = (lower + upper) / 2;
if (query(n1, g - lower, ii1, ii2 + lower))
upper = g;
else
lower = g;
}
j = ii2[lower] - 1;
setRoad(i + 1, j + 1), join(i, j);
}
}
