





"""simple docstring"""




from __future__ import annotations

UpperCamelCase_									={
    """A""": ["""B""", """C""", """E"""],
    """B""": ["""A""", """D""", """E"""],
    """C""": ["""A""", """F""", """G"""],
    """D""": ["""B"""],
    """E""": ["""A""", """B""", """D"""],
    """F""": ["""C"""],
    """G""": ["""C"""],
}




class 			_a						:






				def __init__(			self		:   Union[str, Any],			lowerCAmelCase__		:   dict[str, list[str]],			lowerCAmelCase__		:   str							)     ->				None:




										'''simple docstring'''



										_UpperCamelCase      : Tuple         =   graph
										# mapping node to its parent in resulting breadth first tree
										_UpperCamelCase      : dict[str, str | None]         =   {}
										_UpperCamelCase      : Optional[Any]         =   source_vertex






				def     snake_case     (			self		:   Optional[Any]							)     ->				None:




										'''simple docstring'''



										_UpperCamelCase      : List[str]         =   {self.source_vertex}
										_UpperCamelCase      : str         =   None
										_UpperCamelCase      : Optional[Any]         =   [self.source_vertex]  # first in first out queue

										while queue:
																_UpperCamelCase      : str         =   queue.pop(0							)
																for adjacent_vertex in self.graph[vertex]:
																						if adjacent_vertex not in visited:
																												visited.add(lowerCAmelCase__							)
																												_UpperCamelCase      : Dict         =   vertex
																												queue.append(lowerCAmelCase__							)






				def     snake_case     (			self		:   Tuple,			lowerCAmelCase__		:   str							)     ->				str:




										'''simple docstring'''



										if target_vertex == self.source_vertex:
																return self.source_vertex

										_UpperCamelCase      : Optional[int]         =   self.parent.get(lowerCAmelCase__							)
										if target_vertex_parent is None:
																_UpperCamelCase      : Any         =   (
																    f"""No path from vertex: {self.source_vertex} to vertex: {target_vertex}"""
																)
																raise ValueError(lowerCAmelCase__							)

										return self.shortest_path(lowerCAmelCase__							) + f"""->{target_vertex}"""


if __name__ == "__main__":
						UpperCamelCase_									=Graph(graph, """G""")
						g.breath_first_search()
						print(g.shortest_path("""D"""))
						print(g.shortest_path("""G"""))
						print(g.shortest_path("""Foo"""))










"""simple docstring"""




from functools import lru_cache





@lru_cache
def 	a_    (							_lowercase       ):
						if num < 0:
												raise ValueError('''Number should not be negative.'''       )

						return 1 if num in (0, 1) else num * factorial(num - 1       )


if __name__ == "__main__":
						import doctest

						doctest.testmod()



