





from __future__ import annotations

__lowerCAmelCase :Any     =    {
    '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 ,						__snake_case ,						__snake_case				)      ->      None:


							'''simple docstring'''

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







		def        lowercase       (    self				)      ->      None:


							'''simple docstring'''

							_snake_case       :					Union[str, Any]				       =   {self.source_vertex}
							_snake_case       :					List[str]				       =   None
							_snake_case       :					Dict				       =   [self.source_vertex]  # first in first out queue

							while queue:
												_snake_case       :					Union[str, Any]				       =   queue.pop(0				)
												for adjacent_vertex in self.graph[vertex]:
																	if adjacent_vertex not in visited:
																						visited.add(__snake_case				)
																						_snake_case       :					int				       =   vertex
																						queue.append(__snake_case				)







		def        lowercase       (    self ,						__snake_case				)      ->      str:


							'''simple docstring'''

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

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

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


if __name__ == "__main__":
							__lowerCAmelCase :List[str]     =    Graph(graph, 'G')
							g.breath_first_search()
							print(g.shortest_path('D'))
							print(g.shortest_path('G'))
							print(g.shortest_path('Foo'))






import re







def    A				(							UpperCAmelCase				):
					_snake_case       :					Any				       =   re.compile(R"^(\+91[\-\s]?)?[0]?(91)?[789]\d{9}$"				)
					if match := re.search(UpperCAmelCase  ,  UpperCAmelCase				):
										return match.string == phone
					return False


if __name__ == "__main__":
							print(indian_phone_validator('+918827897895'))