






UpperCAmelCase_									=							{
    "A": ["B", "C", "E"],
    "B": ["A", "D", "E"],
    "C": ["A", "F", "G"],
    "D": ["B"],
    "E": ["A", "B", "D"],
    "F": ["C"],
    "G": ["C"],
}
def 							UpperCAmelCase__		(				_SCREAMING_SNAKE_CASE   :	dict     ,				_SCREAMING_SNAKE_CASE   :	List[Any]     ,				_SCREAMING_SNAKE_CASE   :	Optional[Any]				)->list[str]:
      _lowerCAmelCase 			=  set()
      # keep track of all the paths to be checked
      _lowerCAmelCase 			=  [[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 			=  queue.pop(0				)
            # get the last node from the path
            _lowerCAmelCase 			=  path[-1]
            if node not in explored:
                  _lowerCAmelCase 			=  graph[node]
                  # go through all neighbour nodes, construct a new path and
                  # push it into the queue
                  for neighbour in neighbours:
                        _lowerCAmelCase 			=  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 							UpperCAmelCase__		(				_SCREAMING_SNAKE_CASE   :	dict     ,				_SCREAMING_SNAKE_CASE   :	List[str]     ,				_SCREAMING_SNAKE_CASE   :	Union[str, Any]				)->int:
      if not graph or start not in graph or target not in graph:
            return -1
      if start == target:
            return 0
      _lowerCAmelCase 			=  [start]
      _lowerCAmelCase 			=  set(_SCREAMING_SNAKE_CASE				)
      # Keep tab on distances from `start` node.
      _lowerCAmelCase 			=  {start: 0, target: -1}
      while queue:
            _lowerCAmelCase 			=  queue.pop(0				)
            if node == target:
                  _lowerCAmelCase 			=  (
                      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				)
                        _lowerCAmelCase 			=  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




def 							UpperCAmelCase__		(				_SCREAMING_SNAKE_CASE   :	Optional[Any]				)->Any:  # noqa: E741
      _lowerCAmelCase 			=  len(_SCREAMING_SNAKE_CASE				)
      _lowerCAmelCase 			=  0
      _lowerCAmelCase 			=  [0] * n
      _lowerCAmelCase 			=  [False] * n
      _lowerCAmelCase 			=  [False] * n

      def dfs(_SCREAMING_SNAKE_CASE   :	List[str]     ,				_SCREAMING_SNAKE_CASE   :	List[Any]     ,				_SCREAMING_SNAKE_CASE   :	Optional[int]     ,				_SCREAMING_SNAKE_CASE   :	int				):
            if parent == root:
                  out_edge_count += 1
            _lowerCAmelCase 			=  True
            _lowerCAmelCase 			=  at

            for to in l[at]:
                  if to == parent:
                        pass
                  elif not visited[to]:
                        _lowerCAmelCase 			=  dfs(_SCREAMING_SNAKE_CASE     ,				_SCREAMING_SNAKE_CASE     ,				_SCREAMING_SNAKE_CASE     ,				_SCREAMING_SNAKE_CASE				)
                        _lowerCAmelCase 			=  min(low[at]     ,				low[to]				)

                        # AP found via bridge
                        if at < low[to]:
                              _lowerCAmelCase 			=  True
                        # AP found via cycle
                        if at == low[to]:
                              _lowerCAmelCase 			=  True
                  else:
                        _lowerCAmelCase 			=  min(low[at]     ,				_SCREAMING_SNAKE_CASE				)
            return out_edge_count

      for i in range(_SCREAMING_SNAKE_CASE				):
            if not visited[i]:
                  _lowerCAmelCase 			=  0
                  _lowerCAmelCase 			=  dfs(_SCREAMING_SNAKE_CASE     ,				_SCREAMING_SNAKE_CASE     ,				-1     ,				_SCREAMING_SNAKE_CASE				)
                  _lowerCAmelCase 			=  out_edge_count > 1

      for x in range(len(_SCREAMING_SNAKE_CASE				)				):
            if is_art[x] is True:
                  print(_SCREAMING_SNAKE_CASE				)


# Adjacency list of graph
UpperCAmelCase_									=							{
    0: [1, 2],
    1: [0, 2],
    2: [0, 1, 3, 5],
    3: [2, 4],
    4: [3],
    5: [2, 6, 8],
    6: [5, 7],
    7: [6, 8],
    8: [5, 7],
}


compute_ap(data)