graph = {
    'A': [('B', 'C')],
    'B': [('D',), ('E',)],
    'C': [('F',)],
    'D': [],
    'E': [],
    'F': []
}

heuristic = {
    'A': 1,
    'B': 6,
    'C': 2,
    'D': 0,
    'E': 0,
    'F': 0
}

solution = {}

def ao_star(node):

    if len(graph[node]) == 0:
        solution[node] = []
        return 0

    min_cost = float('inf')

    best_child = None

    for children in graph[node]:

        cost = 0

        for child in children:
            cost += heuristic[child]

        if cost < min_cost:
            min_cost = cost
            best_child = children

    solution[node] = best_child

    return min_cost

ao_star('A')

print("AO* Solution Graph:")

for parent, child in solution.items():
    print(parent, "->", child)