


'''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 	a_					( lowerCamelCase	:     dict	, lowerCamelCase	:     List[str]	, lowerCamelCase	:     Optional[int]				):
   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(lowerCamelCase				)
            new_path.append(lowerCamelCase				)
            queue.append(lowerCamelCase				)
            # return path if neighbour is goal
            if neighbour == goal:
               return new_path

            # mark node as explored
         explored.add(lowerCamelCase				)

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





def 	a_					( lowerCamelCase	:     dict	, lowerCamelCase	:     List[Any]	, lowerCamelCase	:     List[Any]				):
   if not graph or start not in graph or target not in graph:
      return -1
   if start == target:
      return 0
   lowerCAmelCase     =			[start]
   lowerCAmelCase     =			set(lowerCamelCase				)
   # 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(lowerCamelCase				)
            queue.append(lowerCamelCase				)
            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









'''simple docstring'''




class 		UpperCAmelCase_      :





     def __init__( self       :      List[str]    ,      UpperCAmelCase__       :      list[int]    )				->  None:
        lowerCAmelCase     =			len(UpperCAmelCase__    )
        lowerCAmelCase     =			[0] * len_array

        if len_array > 0:
           lowerCAmelCase     =			array[0]

        for i in range(1    ,      UpperCAmelCase__    ):
           lowerCAmelCase     =			self.prefix_sum[i - 1] + array[i]





     def 							__UpperCAmelCase      ( self       :      Optional[Any]    ,      UpperCAmelCase__       :      int    ,      UpperCAmelCase__       :      int    )				->  int:
        if start == 0:
           return self.prefix_sum[end]

        return self.prefix_sum[end] - self.prefix_sum[start - 1]





     def 							__UpperCAmelCase      ( self       :      int    ,      UpperCAmelCase__       :      int    )				->  bool:
        lowerCAmelCase     =			{0}
        for sum_item in self.prefix_sum:
           if sum_item - target_sum in sums:
              return True

           sums.add(UpperCAmelCase__    )

        return False


if __name__ == "__main__":
       import doctest

       doctest.testmod()





