from collections import deque

romania = {
    "A": ["S", "T", "Z"],
    "Z": ["A", "O"],
    "O": ["S", "Z"],
    "T": ["A", "L"],
    "L": ["M", "T"],
    "M": ["D", "L"],
    "D": ["C", "M"],
    "S": ["A", "F", "O", "R"],
    "R": ["C", "P", "S"],
    "C": ["D", "P", "R"],
    "F": ["B", "S"],
    "P": ["B", "C", "R"],
    "B": [],
}

def bfs_gsa(graph, start, goal, trace=False):
    frontier = deque([start])
    explored = set()
    while frontier:
        path = frontier.popleft()
        state = path[-1]
        if state == goal:
            return path
        if state in explored:
            continue
        explored.add(state)
        paths = [path + child for child in graph[state]]
        frontier.extend(paths)
        if trace:
            print(f"{path} -> {list(frontier)}")
            print(f"explored: {sorted(explored)}\n")

print("solution:", bfs_gsa(romania, "A", "B", True))