



from __future__ import annotations

__A       =						{
    '''A''': ['''B''', '''C''', '''E'''],
    '''B''': ['''A''', '''D''', '''E'''],
    '''C''': ['''A''', '''F''', '''G'''],
    '''D''': ['''B'''],
    '''E''': ['''A''', '''B''', '''D'''],
    '''F''': ['''C'''],
    '''G''': ['''C'''],
}






class 		lowercase						:






	"""simple docstring"""


	def __init__(     self     :						Union[str, Any]						,  __UpperCAmelCase     :						dict[str, list[str]]						,  __UpperCAmelCase     :						str					)      ->			str:
							UpperCAmelCase_=       graph
							# mapping node to its parent in resulting breadth first tree
							UpperCAmelCase_=       {}
							UpperCAmelCase_=       source_vertex




	def   _SCREAMING_SNAKE_CASE		(     self     :						int					)      ->			Dict:
							UpperCAmelCase_=       {self.source_vertex}
							UpperCAmelCase_=       None
							UpperCAmelCase_=       [self.source_vertex]  # first in first out queue

							while queue:
													UpperCAmelCase_=       queue.pop(0					)
													for adjacent_vertex in self.graph[vertex]:
																			if adjacent_vertex not in visited:
																									visited.add(_UpperCAmelCase					)
																									UpperCAmelCase_=       vertex
																									queue.append(_UpperCAmelCase					)




	def   _SCREAMING_SNAKE_CASE		(     self     :						Any						,  __UpperCAmelCase     :						str					)      ->			Optional[int]:






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

							UpperCAmelCase_=       self.parent.get(_UpperCAmelCase					)
							if target_vertex_parent is None:
													UpperCAmelCase_=       (
													    F"""No path from vertex: {self.source_vertex} to vertex: {target_vertex}"""
													)
													raise ValueError(_UpperCAmelCase					)

							return self.shortest_path(_UpperCAmelCase					) + F"""->{target_vertex}"""


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









def 	__a					(   lowerCAmelCase_       : Dict    )				->			Dict:






						'''simple docstring'''



						return [
						    {
						        0: [1, 2],
						        1: [0, 2],
						        2: [0, 1, 3, 5],
						        3: [2, 4],
						        4: [3],
						        5: [2, 6, 8],
						        6: [5, 7],
						        7: [6, 8],
						        8: [5, 7],
						    },
						    {
						        0: [6],
						        1: [9],
						        2: [4, 5],
						        3: [4],
						        4: [2, 3],
						        5: [2],
						        6: [0, 7],
						        7: [6],
						        8: [],
						        9: [1],
						    },
						    {
						        0: [4],
						        1: [6],
						        2: [],
						        3: [5, 6, 7],
						        4: [0, 6],
						        5: [3, 8, 9],
						        6: [1, 3, 4, 7],
						        7: [3, 6, 8, 9],
						        8: [5, 7],
						        9: [5, 7],
						    },
						    {
						        0: [1, 3],
						        1: [0, 2, 4],
						        2: [1, 3, 4],
						        3: [0, 2, 4],
						        4: [1, 2, 3],
						    },
						][index]



def 	__a					(   lowerCAmelCase_       : dict[int, list[int]]    )				->			list[tuple[int, int]]:






						'''simple docstring'''



						UpperCAmelCase_=       0
						UpperCAmelCase_=       len(lowerCAmelCase_    )  # No of vertices in graph
						UpperCAmelCase_=       [0] * n
						UpperCAmelCase_=       [False] * n

						def dfs(lowerCAmelCase_       : Optional[int]      ,lowerCAmelCase_       : Dict      ,lowerCAmelCase_       : Any      ,lowerCAmelCase_       : int    ):
												UpperCAmelCase_=       True
												UpperCAmelCase_=       id_
												id_ += 1
												for to in graph[at]:
																		if to == parent:
																								pass
																		elif not visited[to]:
																								dfs(lowerCAmelCase_      ,lowerCAmelCase_      ,lowerCAmelCase_      ,id_    )
																								UpperCAmelCase_=       min(low[at]      ,low[to]    )
																								if id_ <= low[to]:
																														bridges.append((at, to) if at < to else (to, at)    )
																		else:
																								# This edge is a back edge and cannot be a bridge
																								UpperCAmelCase_=       min(low[at]      ,low[to]    )

						UpperCAmelCase_=       []
						for i in range(lowerCAmelCase_    ):
												if not visited[i]:
																		dfs(lowerCAmelCase_      ,-1      ,lowerCAmelCase_      ,id_    )
						return bridges


if __name__ == "__main__":
	import doctest

	doctest.testmod()




