





'''simple docstring'''







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

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

            # mark node as explored
   explored.add(a     )

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

def    __UpperCamelCase	(	a    : dict					,   a    : Tuple					,   a    : str     ) ->int:
 if not graph or start not in graph or target not in graph:
  return -1
 if start == target:
  return 0
 snake_case				=			[start]
 snake_case				=			set(a     )
 # Keep tab on distances from `start` node.
 snake_case				=			{start: 0, target: -1}
 while queue:
  snake_case				=			queue.pop(0     )
  if node == target:
   snake_case				=			(
       dist[node] if dist[target] == -1 else min(dist[target]					,   dist[node]     )
   )
  for adjacent in graph[node]:
   if adjacent not in visited:
    visited.add(a     )
    queue.append(a     )
    snake_case				=			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'''







def    __UpperCamelCase	(	a    : int					,   a    : int     ) ->int:
 while b:
  snake_case				,		snake_case				=			b, a % b
 return a

def    __UpperCamelCase	(	a    : int					,   a    : int     ) ->int:
 return a if b == 0 else euclidean_gcd_recursive(a					,   a % b     )

def    __UpperCamelCase	(	) ->Optional[Any]:
 print(f"""euclidean_gcd(3, 5) = {euclidean_gcd(3					,   5     )}"""     )
 print(f"""euclidean_gcd(5, 3) = {euclidean_gcd(5					,   3     )}"""     )
 print(f"""euclidean_gcd(1, 3) = {euclidean_gcd(1					,   3     )}"""     )
 print(f"""euclidean_gcd(3, 6) = {euclidean_gcd(3					,   6     )}"""     )
 print(f"""euclidean_gcd(6, 3) = {euclidean_gcd(6					,   3     )}"""     )

 print(f"""euclidean_gcd_recursive(3, 5) = {euclidean_gcd_recursive(3					,   5     )}"""     )
 print(f"""euclidean_gcd_recursive(5, 3) = {euclidean_gcd_recursive(5					,   3     )}"""     )
 print(f"""euclidean_gcd_recursive(1, 3) = {euclidean_gcd_recursive(1					,   3     )}"""     )
 print(f"""euclidean_gcd_recursive(3, 6) = {euclidean_gcd_recursive(3					,   6     )}"""     )
 print(f"""euclidean_gcd_recursive(6, 3) = {euclidean_gcd_recursive(6					,   3     )}"""     )


if __name__ == "__main__":
   main()

