



'''simple docstring'''

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






def       __lowercase  (_SCREAMING_SNAKE_CASE      :dict    ,	_SCREAMING_SNAKE_CASE      :Optional[Any]    ,	_SCREAMING_SNAKE_CASE      :Tuple       ):
				SCREAMING_SNAKE_CASE  :						str      					= set()
				# keep track of all the paths to be checked
				SCREAMING_SNAKE_CASE  :						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
								SCREAMING_SNAKE_CASE  :						str      					= queue.pop(0       )
								# get the last node from the path
								SCREAMING_SNAKE_CASE  :						Optional[Any]      					= path[-1]
								if node not in explored:
												SCREAMING_SNAKE_CASE  :						int      					= graph[node]
												# go through all neighbour nodes, construct a new path and
												# push it into the queue
												for neighbour in neighbours:
																SCREAMING_SNAKE_CASE  :						List[str]      					= list(_SCREAMING_SNAKE_CASE       )
																new_path.append(_SCREAMING_SNAKE_CASE       )
																queue.append(_SCREAMING_SNAKE_CASE       )
																# return path if neighbour is goal
																if neighbour == goal:
																				return new_path

            # mark node as explored
												explored.add(_SCREAMING_SNAKE_CASE       )

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






def       __lowercase  (_SCREAMING_SNAKE_CASE      :dict    ,	_SCREAMING_SNAKE_CASE      :Union[str, Any]    ,	_SCREAMING_SNAKE_CASE      :Dict       ):
				if not graph or start not in graph or target not in graph:
								return -1
				if start == target:
								return 0
				SCREAMING_SNAKE_CASE  :						Optional[Any]      					= [start]
				SCREAMING_SNAKE_CASE  :						Any      					= set(_SCREAMING_SNAKE_CASE       )
				# Keep tab on distances from `start` node.
				SCREAMING_SNAKE_CASE  :						List[str]      					= {start: 0, target: -1}
				while queue:
								SCREAMING_SNAKE_CASE  :						List[Any]      					= queue.pop(0       )
								if node == target:
												SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= (
												    dist[node] if dist[target] == -1 else min(dist[target]    ,	dist[node]       )
												)
								for adjacent in graph[node]:
												if adjacent not in visited:
																visited.add(_SCREAMING_SNAKE_CASE       )
																queue.append(_SCREAMING_SNAKE_CASE       )
																SCREAMING_SNAKE_CASE  :						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









'''simple docstring'''

from manim import *


class 	a__     (				_lowercase	):


	def 				lowercase__  (self : Optional[Any]      )     ->			str:

					"""simple docstring"""

					SCREAMING_SNAKE_CASE  :						List[Any]      					= Rectangle(height=0.5,					width=0.5      )
					SCREAMING_SNAKE_CASE  :						str      					= Rectangle(height=0.46,					width=0.46      ).set_stroke(width=0      )

					SCREAMING_SNAKE_CASE  :						List[str]      					= [mem.copy() for i in range(6      )]
					SCREAMING_SNAKE_CASE  :						Optional[int]      					= [mem.copy() for i in range(6      )]
					SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= VGroup(*__UpperCAmelCase      ).arrange(__UpperCAmelCase,					buff=0      )
					SCREAMING_SNAKE_CASE  :						List[str]      					= VGroup(*__UpperCAmelCase      ).arrange(__UpperCAmelCase,					buff=0      )
					SCREAMING_SNAKE_CASE  :						List[Any]      					= VGroup(__UpperCAmelCase,					__UpperCAmelCase      ).arrange(__UpperCAmelCase,					buff=0      )
					SCREAMING_SNAKE_CASE  :						Tuple      					= Text('''CPU''',					font_size=24      )
					SCREAMING_SNAKE_CASE  :						Dict      					= Group(__UpperCAmelCase,					__UpperCAmelCase      ).arrange(__UpperCAmelCase,					buff=0.5,					aligned_edge=__UpperCAmelCase      )
					cpu.move_to([-2.5, -0.5, 0]      )
					self.add(__UpperCAmelCase      )

					SCREAMING_SNAKE_CASE  :						Any      					= [mem.copy() for i in range(1      )]
					SCREAMING_SNAKE_CASE  :						Dict      					= VGroup(*__UpperCAmelCase      ).arrange(__UpperCAmelCase,					buff=0      )
					SCREAMING_SNAKE_CASE  :						List[str]      					= Text('''GPU''',					font_size=24      )
					SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= Group(__UpperCAmelCase,					__UpperCAmelCase      ).arrange(__UpperCAmelCase,					buff=0.5,					aligned_edge=__UpperCAmelCase      )
					gpu.align_to(__UpperCAmelCase,					__UpperCAmelCase      )
					gpu.set_x(gpu.get_x() - 1      )

					self.add(__UpperCAmelCase      )

					SCREAMING_SNAKE_CASE  :						List[Any]      					= [mem.copy() for i in range(6      )]
					SCREAMING_SNAKE_CASE  :						Any      					= VGroup(*__UpperCAmelCase      ).arrange(__UpperCAmelCase,					buff=0      )

					SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= Text('''Model''',					font_size=24      )
					SCREAMING_SNAKE_CASE  :						Dict      					= Group(__UpperCAmelCase,					__UpperCAmelCase      ).arrange(__UpperCAmelCase,					buff=0.5,					aligned_edge=__UpperCAmelCase      )
					model.move_to([3, -1.0, 0]      )

					self.play(
					    Create(__UpperCAmelCase,					run_time=1      ),					Create(__UpperCAmelCase,					run_time=1      ),					Create(__UpperCAmelCase,					run_time=1      ),					)

					SCREAMING_SNAKE_CASE  :						Tuple      					= MarkupText(
					    F'''First, an empty model skeleton is loaded\ninto <span fgcolor=\'{YELLOW}\'>memory</span> without using much RAM.''',					font_size=24,					)

					SCREAMING_SNAKE_CASE  :						Optional[Any]      					= Square(side_length=2.2      )
					key.move_to([-5, 2, 0]      )

					SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= MarkupText(
					    F'''<b>Key:</b>\n\n<span fgcolor=\'{YELLOW}\'>●</span> Empty Model''',					font_size=18,					)

					key_text.move_to([-5, 2.4, 0]      )

					step_a.move_to([2, 2, 0]      )
					self.play(Write(__UpperCAmelCase,					run_time=2.5      ),					Write(__UpperCAmelCase      ),					Write(__UpperCAmelCase      )      )

					self.add(__UpperCAmelCase      )

					SCREAMING_SNAKE_CASE  :						List[str]      					= []
					SCREAMING_SNAKE_CASE  :						List[str]      					= []
					SCREAMING_SNAKE_CASE  :						Dict      					= []
					for i, rect in enumerate(__UpperCAmelCase      ):
									SCREAMING_SNAKE_CASE  :						Optional[int]      					= Rectangle(height=0.46,					width=0.46      ).set_stroke(width=0.0      ).set_fill(__UpperCAmelCase,					opacity=0.7      )
									cpu_target.move_to(__UpperCAmelCase      )
									cpu_target.generate_target()
									SCREAMING_SNAKE_CASE  :						List[str]      					= 0.46 / 4
									SCREAMING_SNAKE_CASE  :						Any      					= 0.46 / 3

									if i == 0:
													cpu_target.target.next_to(cpu_left_col_base[0].get_corner(DOWN + LEFT      ),					buff=0.02,					direction=__UpperCAmelCase      )
													cpu_target.target.set_x(cpu_target.target.get_x() + 0.1      )
									elif i == 3:
													cpu_target.target.next_to(cpu_targs[0].target,					direction=__UpperCAmelCase,					buff=0.0      )
									else:
													cpu_target.target.next_to(cpu_targs[i - 1].target,					direction=__UpperCAmelCase,					buff=0.0      )
									cpu_targs.append(__UpperCAmelCase      )

									first_animations.append(rect.animate(run_time=0.5      ).set_stroke(__UpperCAmelCase      )      )
									second_animations.append(MoveToTarget(__UpperCAmelCase,					run_time=1.5      )      )

					self.play(*__UpperCAmelCase      )
					self.play(*__UpperCAmelCase      )

					self.wait()




