






from __future__ import annotations

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


class   __SCREAMING_SNAKE_CASE:
							def __init__(     self:      Optional[int]       ,	UpperCamelCase:      dict[str, list[str]]       ,	UpperCamelCase:      str						)		->		None:
											snake_case__									=     graph
											# mapping node to its parent in resulting breadth first tree
											snake_case__									=     {}
											snake_case__									=     source_vertex
							def lowerCAmelCase_ (     self:      List[str]						)		->		None:
											snake_case__									=     {self.source_vertex}
											snake_case__									=     None
											snake_case__									=     [self.source_vertex]  # first in first out queue

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


							def lowerCAmelCase_ (     self:      str       ,	UpperCamelCase:      str						)		->		str:
											if target_vertex == self.source_vertex:
															return self.source_vertex

											snake_case__									=     self.parent.get(UpperCamelCase						)
											if target_vertex_parent is None:
															snake_case__									=     (
															    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__":
							__UpperCamelCase					:		Dict	  =						Graph(graph, """G""")
							g.breath_first_search()
							print(g.shortest_path("""D"""))
							print(g.shortest_path("""G"""))
							print(g.shortest_path("""Foo"""))












from __future__ import annotations
def      a_ (      _A      ,   _A  )			->			str:







				"""simple docstring"""
				# Checks if the entire collection has been sorted
				if len(_A  ) <= 1 or n <= 1:
								return

				insert_next(_A      ,   n - 1  )
				rec_insertion_sort(_A      ,   n - 1  )
def      a_ (      _A      ,   _A  )			->			Tuple:







				"""simple docstring"""
				# Checks order between adjacent elements
				if index >= len(_A  ) or collection[index - 1] <= collection[index]:
								return

				# Swaps adjacent elements since they are not in ascending order
				snake_case__							,						snake_case__									=     (
				    collection[index],
				    collection[index - 1],
				)

				insert_next(_A      ,   index + 1  )


if __name__ == "__main__":
							__UpperCamelCase					:		Optional[int]	  =						input("""Enter integers separated by spaces: """)
							__UpperCamelCase					:		list[int]	  =						[int(num) for num in numbers.split()]
							rec_insertion_sort(number_list, len(number_list))
							print(number_list)




