





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





def 	lowerCAmelCase_					(			__a      ,       __a      ,       __a						)	->						list[str]:







  """simple docstring"""





  lowerCamelCase__: Optional[int]         =set()
  # keep track of all the paths to be checked
  lowerCamelCase__: Tuple         =[[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
    lowerCamelCase__: Optional[Any]         =queue.pop(0						)
    # get the last node from the path
    lowerCamelCase__: Any         =path[-1]
    if node not in explored:
      lowerCamelCase__: Tuple         =graph[node]
      # go through all neighbour nodes, construct a new path and
      # push it into the queue
      for neighbour in neighbours:
        lowerCamelCase__: Any         =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 	lowerCAmelCase_					(			__a      ,       __a      ,       __a						)	->						int:







  """simple docstring"""





  if not graph or start not in graph or target not in graph:
    return -1
  if start == target:
    return 0
  lowerCamelCase__: Tuple         =[start]
  lowerCamelCase__: str         =set(__a						)
  # Keep tab on distances from `start` node.
  lowerCamelCase__: Any         ={start: 0, target: -1}
  while queue:
    lowerCamelCase__: List[Any]         =queue.pop(0						)
    if node == target:
      lowerCamelCase__: List[str]         =(
          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						)
        lowerCamelCase__: Optional[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 timeit import timeit

__UpperCamelCase   :							int         =   {
    """MALAYALAM""": True,
    """String""": False,
    """rotor""": True,
    """level""": True,
    """A""": True,
    """BB""": True,
    """ABC""": False,
    """amanaplanacanalpanama""": True,  # "a man a plan a canal panama"
}
# Ensure our test data is valid
assert all((key == key[::-1]) is value for key, value in test_data.items())



def  __UpperCAmelCase						(					SCREAMING_SNAKE_CASE__:						str     )	->      bool:

   """simple docstring"""
   __a					  =     0
   __a					  =     len(SCREAMING_SNAKE_CASE__     ) - 1
   while start_i < end_i:
      if s[start_i] == s[end_i]:
         start_i += 1
         end_i -= 1
      else:
         return False
   return True



def  __UpperCAmelCase						(					SCREAMING_SNAKE_CASE__:						str     )	->      bool:

   """simple docstring"""
   __a					  =     len(SCREAMING_SNAKE_CASE__     ) // 2
   __a					  =     len(SCREAMING_SNAKE_CASE__     )

   # We need to traverse till half of the length of string
   # as we can get access of the i'th last element from
   # i'th index.
   # eg: [0,1,2,3,4,5] => 4th index can be accessed
   # with the help of 1st index (i==n-i-1)
   # where n is length of string
   return all(s[i] == s[n - i - 1] for i in range(SCREAMING_SNAKE_CASE__     )     )



def  __UpperCAmelCase						(					SCREAMING_SNAKE_CASE__:						str     )	->      bool:

   """simple docstring"""
   if len(SCREAMING_SNAKE_CASE__     ) <= 2:
      return True
   if s[0] == s[len(SCREAMING_SNAKE_CASE__     ) - 1]:
      return is_palindrome_recursive(s[1:-1]     )
   else:
      return False



def  __UpperCAmelCase						(					SCREAMING_SNAKE_CASE__:						str     )	->      bool:

   """simple docstring"""
   return s == s[::-1]



def  __UpperCAmelCase						(					SCREAMING_SNAKE_CASE__:						str     )	->      None:

   """simple docstring"""
   __a					  =     f"""all({name}(key) is value for key, value in test_data.items())"""
   __a					  =     f"""from __main__ import test_data, {name}"""
   __a					  =     500000
   __a					  =     timeit(stmt=SCREAMING_SNAKE_CASE__,       setup=SCREAMING_SNAKE_CASE__,       number=SCREAMING_SNAKE_CASE__     )
   print(f"""{name:<35} finished {number:,} runs in {result:.5f} seconds"""     )


if __name__ == "__main__":
 for key, value in test_data.items():
  assert is_palindrome(key) is is_palindrome_recursive(key)
  assert is_palindrome(key) is is_palindrome_slice(key)
  print(f"""{key:21} {value}""")
 print("""a man a plan a canal panama""")

 # finished 500,000 runs in 0.46793 seconds
 benchmark_function("""is_palindrome_slice""")
 # finished 500,000 runs in 0.85234 seconds
 benchmark_function("""is_palindrome""")
 # finished 500,000 runs in 1.32028 seconds
 benchmark_function("""is_palindrome_recursive""")
 # finished 500,000 runs in 2.08679 seconds
 benchmark_function("""is_palindrome_traversal""")