
__lowerCAmelCase					:			List[str]			      =		{
    "A": ["B", "C", "E"],
    "B": ["A", "D", "E"],
    "C": ["A", "F", "G"],
    "D": ["B"],
    "E": ["A", "B", "D"],
    "F": ["C"],
    "G": ["C"],
}


def     UpperCAmelCase_  (						__lowerCAmelCase	,					__lowerCAmelCase	,					__lowerCAmelCase	) ->						list[str]:
    __lowercase		:			Optional[int]	    =       set()
    # keep track of all the paths to be checked
    __lowercase		:			Dict	    =       [[start]]

    # return path if start is goal
    if start == goal:
        return [start]

    # keeps looping until all possible paths have been checked
    while queue:
        # pop the first path from the queue
        __lowercase		:			Union[str, Any]	    =       queue.pop(0	)
        # get the last node from the path
        __lowercase		:			Optional[int]	    =       path[-1]
        if node not in explored:
            __lowercase		:			Dict	    =       graph[node]
            # go through all neighbour nodes, construct a new path and
            # push it into the queue
            for neighbour in neighbours:
                __lowercase		:			List[str]	    =       list(__lowerCAmelCase	)
                new_path.append(__lowerCAmelCase	)
                queue.append(__lowerCAmelCase	)
                # return path if neighbour is goal
                if neighbour == goal:
                    return new_path

            # mark node as explored
            explored.add(__lowerCAmelCase	)

    # in case there's no path between the 2 nodes
    return []


def     UpperCAmelCase_  (						__lowerCAmelCase	,					__lowerCAmelCase	,					__lowerCAmelCase	) ->						int:

    if not graph or start not in graph or target not in graph:
        return -1
    if start == target:
        return 0
    __lowercase		:			List[str]	    =       [start]
    __lowercase		:			Optional[Any]	    =       set(__lowerCAmelCase	)
    # Keep tab on distances from `start` node.
    __lowercase		:			Optional[Any]	    =       {start: 0, target: -1}
    while queue:
        __lowercase		:			Any	    =       queue.pop(0	)
        if node == target:
            __lowercase		:			Optional[int]	    =       (
                dist[node] if dist[target] == -1 else min(dist[target]	,					dist[node]	)
            )
        for adjacent in graph[node]:
            if adjacent not in visited:
                visited.add(__lowerCAmelCase	)
                queue.append(__lowerCAmelCase	)
                __lowercase		:			Optional[int]	    =       dist[node] + 1
    return dist[target]


if __name__ == "__main__":
     print(bfs_shortest_path(demo_graph, "G", "D"))  # returns ['G', 'C', 'A', 'B', 'D']
     print(bfs_shortest_path_distance(demo_graph, "G", "D"))  # returns 4




def     UpperCAmelCase_  (						__lowerCAmelCase	) ->						int:

    if not isinstance(__lowerCAmelCase	,					__lowerCAmelCase	):
        raise ValueError('''multiplicative_persistence() only accepts integral values'''	)
    if num < 0:
        raise ValueError('''multiplicative_persistence() does not accept negative values'''	)

    __lowercase		:			Dict	    =       0
    __lowercase		:			Optional[int]	    =       str(__lowerCAmelCase	)

    while len(__lowerCAmelCase	) != 1:
        __lowercase		:			str	    =       [int(__lowerCAmelCase	) for i in num_string]

        __lowercase		:			Union[str, Any]	    =       1
        for i in range(0	,					len(__lowerCAmelCase	)	):
            total *= numbers[i]

        __lowercase		:			Any	    =       str(__lowerCAmelCase	)

        steps += 1
    return steps


def     UpperCAmelCase_  (						__lowerCAmelCase	) ->						int:

    if not isinstance(__lowerCAmelCase	,					__lowerCAmelCase	):
        raise ValueError('''additive_persistence() only accepts integral values'''	)
    if num < 0:
        raise ValueError('''additive_persistence() does not accept negative values'''	)

    __lowercase		:			Any	    =       0
    __lowercase		:			Union[str, Any]	    =       str(__lowerCAmelCase	)

    while len(__lowerCAmelCase	) != 1:
        __lowercase		:			List[str]	    =       [int(__lowerCAmelCase	) for i in num_string]

        __lowercase		:			Tuple	    =       0
        for i in range(0	,					len(__lowerCAmelCase	)	):
            total += numbers[i]

        __lowercase		:			List[str]	    =       str(__lowerCAmelCase	)

        steps += 1
    return steps


if __name__ == "__main__":
 import doctest

 doctest.testmod()


