



"""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 			snake_case		(		lowerCAmelCase_  ,						lowerCAmelCase_  ,						lowerCAmelCase_	)						->				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(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 			snake_case		(		lowerCAmelCase_  ,						lowerCAmelCase_  ,						lowerCAmelCase_	)						->				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(lowerCAmelCase_	)
  # 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(lowerCAmelCase_	)
        queue.append(lowerCAmelCase_	)
        _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"""






from copy import deepcopy



class     UpperCAmelCase    :



   def __init__(       self    :	Optional[Any]							,       __lowerCamelCase    :	list[int] | None = None							,       __lowerCamelCase    :	int | None = None				):



     """simple docstring"""

     if arr is None and size is not None:
       _snake_case   	=      size
       _snake_case   	=      [0] * size
     elif arr is not None:
       self.init(__lowerCamelCase				)
     else:
       raise ValueError('''Either arr or size must be specified'''				)



   def    __UpperCAmelCase    (       self    :	Any							,       __lowerCamelCase    :	list[int]				):



     """simple docstring"""
     _snake_case   	=      len(__lowerCamelCase				)
     _snake_case   	=      deepcopy(__lowerCamelCase				)
     for i in range(1							,       self.size				):
       _snake_case   	=      self.next_(__lowerCamelCase				)
       if j < self.size:
         self.tree[j] += self.tree[i]



   def    __UpperCAmelCase    (       self    :	Union[str, Any]				):



     """simple docstring"""
     _snake_case   	=      self.tree[:]
     for i in range(self.size - 1							,       0							,       -1				):
       _snake_case   	=      self.next_(__lowerCamelCase				)
       if j < self.size:
         arr[j] -= arr[i]
     return arr



   @staticmethod
   def    __UpperCAmelCase    (       __lowerCamelCase    :	int				):



     """simple docstring"""
     return index + (index & (-index))



   @staticmethod
   def    __UpperCAmelCase    (       __lowerCamelCase    :	int				):



     """simple docstring"""
     return index - (index & (-index))



   def    __UpperCAmelCase    (       self    :	Dict							,       __lowerCamelCase    :	int							,       __lowerCamelCase    :	int				):



     """simple docstring"""
     if index == 0:
       self.tree[0] += value
       return
     while index < self.size:
       self.tree[index] += value
       _snake_case   	=      self.next_(__lowerCamelCase				)



   def    __UpperCAmelCase    (       self    :	List[str]							,       __lowerCamelCase    :	int							,       __lowerCamelCase    :	int				):



     """simple docstring"""
     self.add(__lowerCamelCase							,       value - self.get(__lowerCamelCase				)				)



   def    __UpperCAmelCase    (       self    :	Optional[Any]							,       __lowerCamelCase    :	int				):



     """simple docstring"""
     if right == 0:
       return 0
     _snake_case   	=      self.tree[0]
     right -= 1  # make right inclusive
     while right > 0:
       result += self.tree[right]
       _snake_case   	=      self.prev(__lowerCamelCase				)
     return result



   def    __UpperCAmelCase    (       self    :	str							,       __lowerCamelCase    :	int							,       __lowerCamelCase    :	int				):



     """simple docstring"""
     return self.prefix(__lowerCamelCase				) - self.prefix(__lowerCamelCase				)



   def    __UpperCAmelCase    (       self    :	List[str]							,       __lowerCamelCase    :	int				):



     """simple docstring"""
     return self.query(__lowerCamelCase							,       index + 1				)





   def    __UpperCAmelCase    (       self    :	Optional[int]							,       __lowerCamelCase    :	int				):



     """simple docstring"""
     value -= self.tree[0]
     if value < 0:
       return -1

     _snake_case   	=      1  # Largest power of 2 <= size
     while j * 2 < self.size:
       j *= 2

     _snake_case   	=      0

     while j > 0:
       if i + j < self.size and self.tree[i + j] <= value:
         value -= self.tree[i + j]
         i += j
       j //= 2
     return i


if __name__ == "__main__":
     import doctest

     doctest.testmod()





