#include <stdio.h>
#include <strings.h>

#define NO	0
#define YES	!NO
#define TABS	"                                        "

#define STRING(len)	((char *) malloc(len + 1))

#define BADARGS	1

int colors, maxlen;
int gotten = 0;

main(argc,argv)
int argc;
char *argv[];
{
void makenodes();

if (argc < 2)
  {
  fprintf(stderr,"Usage: %s maxlen [colors]\n",argv[0]);
  exit(BADARGS);
  }
else if (argc > 2)
  colors = atoi(argv[2]);
else
  colors = 2;

maxlen = atoi(argv[1]);

makenodes(maxlen,"");
}

/***********************************************************************/
void
makenodes(howfar,s)
int howfar;
char *s;
{
int i, apchk(), ls;
char *newarg;

#ifdef DIAG
printf("%s makenoding with string %s, depth %d.\n",
	TABS+12-maxlen+howfar,s,maxlen-howfar);
#endif

if (howfar == 0)
  {
  printf("%s\n",s);
  return;
  }

for (i=0; i<colors; i++)
  if (!apchk(s,'A'+i))
    {
    ls = strlen(s);
    newarg = STRING(ls + 1);
    if (!newarg) 
      {
      fprintf(stderr,"Couldn't get %d bytes for newarg in makenodes\n",ls+2);
      fprintf(stderr,"Total get was %d.\n",gotten);
      fprintf(stderr,"P\n L\n  O\n   P\n    !\n");
      abort();
      }
    strcpy(newarg,s);
    newarg[ls+1] = '\0';
    newarg[ls] = 'A' + i;
    makenodes(howfar-1,newarg);
    free(newarg);
    }
}

/***********************************************************************/
int
apchk(qq,q)
char *qq ,q;
{
int lqq, f, s, t;

t = lqq = strlen(qq);
if (lqq < 2) return NO;

for (f=lqq % 2; f <= lqq - 2; f += 2)
  {
  s = (f + t) / 2;
  if ((qq[f] == qq[s]) && (qq[s] == q))
    {
#ifdef DIAG
    printf("%s%c is rejected for %c in positions %d,%d,%d.\n",
	qq,q,q,f,s,t);
#endif
    return YES;
    }
  }
return NO;
}