





'''simple docstring'''





UpperCamelCase_						:      List[str]       =						{
    '''A''': ['''B''', '''C''', '''E'''],
    '''B''': ['''A''', '''D''', '''E'''],
    '''C''': ['''A''', '''F''', '''G'''],
    '''D''': ['''B'''],
    '''E''': ['''A''', '''B''', '''D'''],
    '''F''': ['''C'''],
    '''G''': ['''C'''],
}





def      __a     (       _UpperCamelCase:   dict ,						_UpperCamelCase:   Union[str, Any] ,						_UpperCamelCase:   int   )						->			list[str]:

     """simple docstring"""




     _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(_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      __a     (       _UpperCamelCase:   dict ,						_UpperCamelCase:   int ,						_UpperCamelCase:   List[Any]   )						->			int:

     """simple docstring"""




     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(_UpperCamelCase   )
     # 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(_UpperCamelCase   )
                    queue.append(_UpperCamelCase   )
                    _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 __future__ import annotations

from typing import Any





def      __a     (       _UpperCamelCase:   list[Any]   )						->			None:

     """simple docstring"""




     create_state_space_tree(_UpperCamelCase ,						[] ,						0   )





def      __a     (       _UpperCamelCase:   list[Any] ,						_UpperCamelCase:   list[Any] ,						_UpperCamelCase:   int   )						->			None:

     """simple docstring"""




     if index == len(_UpperCamelCase   ):
          print(_UpperCamelCase   )
          return

     create_state_space_tree(_UpperCamelCase ,						_UpperCamelCase ,						index + 1   )
     current_subsequence.append(sequence[index]   )
     create_state_space_tree(_UpperCamelCase ,						_UpperCamelCase ,						index + 1   )
     current_subsequence.pop()


if __name__ == "__main__":
   UpperCamelCase_						:      list[Any]       =						[3, 1, 2, 4]
   generate_all_subsequences(seq)

   seq.clear()
   seq.extend(['''A''', '''B''', '''C'''])
   generate_all_subsequences(seq)


