
"""simple docstring"""




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




def  _lowerCAmelCase		(		_UpperCamelCase ,				_UpperCamelCase ,				_UpperCamelCase						):






  """simple docstring"""



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

            # mark node as explored
      explored.add(_UpperCamelCase						)

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




def  _lowerCAmelCase		(		_UpperCamelCase ,				_UpperCamelCase ,				_UpperCamelCase						):






  """simple docstring"""



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




def  _lowerCAmelCase		(		_UpperCamelCase ,				_UpperCamelCase						):






  """simple docstring"""



  return number | (1 << position)




def  _lowerCAmelCase		(		_UpperCamelCase ,				_UpperCamelCase						):






  """simple docstring"""



  return number & ~(1 << position)




def  _lowerCAmelCase		(		_UpperCamelCase ,				_UpperCamelCase						):






  """simple docstring"""



  return number ^ (1 << position)




def  _lowerCAmelCase		(		_UpperCamelCase ,				_UpperCamelCase						):






  """simple docstring"""



  return ((number >> position) & 1) == 1




def  _lowerCAmelCase		(		_UpperCamelCase ,				_UpperCamelCase						):






  """simple docstring"""



  return int((number & (1 << position)) != 0						)


if __name__ == "__main__":
  import doctest

  doctest.testmod()
