#include "stdio.h"
#include "malloc.h"

#define MAX_NR_THEOREMS 1000
struct 
{	char *theorem;
	int depth;
	int reached;
	int loopcandidate;
	int nodouble;
} theorems[MAX_NR_THEOREMS];
int nr_theorems;

void add(char *theorem, int depth, int p)
{
	if (p) printf(" %s", theorem);
	for (int i = 0; i < nr_theorems; i++)
		if (strcmp(theorem, theorems[i].theorem) == 0)
		{	theorems[i].reached++;
			//printf("-%d-%d", depth, theorems[i].depth);
			if (theorems[i].depth < depth && theorems[i].nodouble == 0)
			{	if (p) printf("*");
				theorems[i].loopcandidate++;
			}
			else
				if (p) printf("#");
			return;
		}
	if (nr_theorems < MAX_NR_THEOREMS)
	{
		theorems[nr_theorems].theorem = (char*)malloc(strlen(theorem)+1);
		strcpy(theorems[nr_theorems].theorem, theorem);
		theorems[nr_theorems].depth = depth;
		theorems[nr_theorems].loopcandidate = 0;
		theorems[nr_theorems].nodouble = 0;
		nr_theorems++;
	}
}

main()
{
	theorems[0].theorem = "MI";
	theorems[0].depth = 0;
	theorems[0].reached = 0;
	theorems[0].loopcandidate = 0;
	theorems[0].nodouble = 0;
	nr_theorems = 1;
	
	for (int i = 0; i < nr_theorems; )
	{
		int j = i;
		for (; i < nr_theorems; i++)
		{
			char *theorem = theorems[i].theorem;
			int len = strlen(theorem);
			int depth = theorems[i].depth;
			char newtheorem[40000];
			int cur_th = i;
	
			printf("%2d expand %s:", depth, theorem);
			
			if (len >= 20000)
				printf(" --skipped\n");
			else
			{
				int expanded = 0;
				
				// try MxIIIy -> MxUy
				for (int i = 1; i <= len-3; i++)
				{
					if (theorem[i] == 'I' && theorem[i+1] == 'I' && theorem[i+2] == 'I')
					{
						expanded = 1;
						strcpy(newtheorem, theorem);
						newtheorem[i] = 'U';
						strcpy(newtheorem+i+1, theorem+i+3);
						add(newtheorem, depth, 1);
					}
				}
				// try MxUUy -> Mxy
				for (int i = 1; i <= len-2; i++)
				{
					if (theorem[i] == 'U' && theorem[i+1] == 'U')
					{
						expanded = 1;
						strcpy(newtheorem, theorem);
						strcpy(newtheorem+i, theorem+i+2);
						add(newtheorem, depth, 1);
					}
				}
			
				// try MxI -> MxIU
				if (theorem[len-1] == 'I')
				{
					expanded = 1;
					strcpy(newtheorem, theorem);
					newtheorem[len] = 'U';
					newtheorem[len+1] = '\0';
					add(newtheorem, depth, 1);	
				}
				
				printf(" %s%s", theorem, theorem+1);
				if (expanded == 0 && theorem[1] != theorem[len-1])
				{	printf("-dead!");
					theorems[cur_th].nodouble = 1;
				}
				printf("\n");
			}
		}
		
		int k = nr_theorems;
		for (; j < k; j++)
		{					
			char *theorem = theorems[j].theorem;
			int len = strlen(theorem);
			int depth = theorems[j].depth + 1;
			char newtheorem[40000];
	
			if (len < 20000 && theorems[j].nodouble == 0)
			{	
				// do Mx -> Mxx
				strcpy(newtheorem, theorem);
				strcpy(newtheorem+len, theorem+1);
				add(newtheorem, depth, 0);
			}
		}
	}
}

/*
MI			-> M(IU) MII
MII			-> M(IIU) MIIII
MUI			-> MUIU MUIUI
MUIU		-> MUIUUIU
MIIII		-> MUI M(IU) MIIIIIIII
MUIUI		-> MUIUIU MUIUIUIUI
MUIIU		-> MUIIUUIIU
MUIUIU		-> MUIUIUUIUIU
MUIIIII		-> MUUII MUIUI MUIIU MUIIIIU MUIIIIIUIIIII
MIUIIII		-> MIUUI MIUIU MIUIIIIU MIUIIIIIUIIII
MIIUIII		-> MIIUU MIIUIIIU MIIUIIIIIUIII
MIIIUII		-> MUUII MIIIUIIU MIIIUIIIIIUII
MIIIIUI		-> MUIUI MIUUI MIIIIUIU MIIIIUIIIIIUI
MIIIIIU		-> MUIIU MIUIU MIIIIIUIIIIIU
MUIUUIU		-> MUIIU MUIUUIUUIUUIU
MIIIIIIII	-> MUIIIII MIUIIII MIIUIII MIIIUII MIIIIUI MIIIIIU
MUIIUUIIU	-> MUIIIIU MUIIUUIIUUIIUUIIU
MUIUIUIUI
MUIUIUUIUIU -> MUIUIIUIU MUIUIUUIUIUUIUIUUIUIU
MUIUUIUUIUUIU
MUIIUUIIUUIIUUIIU
MUIUIUUIUIUUIUIUUIUIU
*/