#include "common.h"

#define VZ 520	/* max no. vertices */
#define SZ 32	/* max set size */

static char names[VZ][3];
static char adj[VZ][VZ];
static int nvert;

static int
to_id(const char *name)
{
	int i;

	for (i=0; i<nvert; i++)
		if (!strcmp(name, names[i]))
			return i;

	assert(nvert < VZ);
	assert(strlen(name) < LEN(*names));

	snprintf(names[nvert++], sizeof(*names), "%s", name);
	return i;
}

static int
cmp_id(const void *a, const void *b)
{
	return strcmp(names[*(int*)a], names[*(int*)b]);
}

/*
 * Construct all unique combinations of nodes, with every extension,
 * confirm they're all connected. Essentally this but recursive:
 *
 *   for (a=0; a<nvert; a++)
 *   for (b=a+1; b<nvert; b++)
 *   for (c=b+1; c<nvert; c++)
 *     ...
 *
 * Note the inner loops continue forward from the point of the outside
 * loop, avoiding duplicate combinations.
 *
 * 'set' and 'best' are arrays of size SZ, length 'sz' and 'bz'. 'set'
 * is the current working state; 'best' is a copy of the longest known
 * set.
 */
static int
max_set(int *set, int sz, int *best, int bz)
{
	int bz1, v,i;

	assert(sz < SZ);

	/* for each potential candidate */
	for (v = sz ? set[sz-1]+1 : 0; v < nvert; v++) {
		 /* adjacent to all in current set? */
		for (i=0; i<sz && adj[set[i]][v]; i++) ;
		if (i != sz) continue;
		 /* recur and update 'best size' if needed */
		set[sz] = v;
		if (bz < (bz1 = max_set(set, sz+1, best, bz))) bz = bz1;
	}

	/* store longest known set in 'best' */
	if (sz > bz)
		memcpy(best, set, (bz = sz) * sizeof(*best));

	return bz;
}

int
main(int argc, char **argv)
{
	static int set[SZ], best[SZ];
	char buf[8];
	int p1=0, a,b,c, i, bz;

	if (argc > 1)
		DISCARD(freopen(argv[1], "r", stdin));
	
	while (fgets(buf, sizeof(buf), stdin)) {
		assert(strlen(buf) >= 5);
		buf[2] = buf[5] = '\0';
		a = to_id(buf);
		b = to_id(buf+3);
		adj[a][b] = adj[b][a] = 1;
	}

	for (a=0; a<nvert; a++)
	for (b=a+1; b<nvert; b++)
	for (c=b+1; c<nvert; c++)
		p1 += adj[a][b] && adj[a][c] && adj[b][c] && (
		      names[a][0] == 't' || names[b][0] == 't' ||
		      names[c][0] == 't');

	printf("23: %d ", p1);

	bz = max_set(set, 0, best, 0);
	qsort(best, bz, sizeof(*best), cmp_id);

	for (i=0; i<bz; i++)
		printf(i ? ",%s" : "%s", names[best[i]]);

	putchar('\n');
	return 0;
}