'''simple docstring'''

lowerCAmelCase_ : Optional[Any]						  =      {
    "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			:						Tuple ,		__lowerCamelCase			:						Any				)	->							list[str]:
      '''simple docstring'''


      lowercase_     =      set()
      # keep track of all the paths to be checked
      lowercase_     =      [[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_     =      queue.pop(0				)
            # get the last node from the path
            lowercase_     =      path[-1]
            if node not in explored:
                  lowercase_     =      graph[node]
                  # go through all neighbour nodes, construct a new path and
                  # push it into the queue
                  for neighbour in neighbours:
                        lowercase_     =      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			:						Dict ,		__lowerCamelCase			:						Tuple				)	->							int:
      '''simple docstring'''


      if not graph or start not in graph or target not in graph:
            return -1
      if start == target:
            return 0
      lowercase_     =      [start]
      lowercase_     =      set(__lowerCamelCase				)
      # Keep tab on distances from `start` node.
      lowercase_     =      {start: 0, target: -1}
      while queue:
            lowercase_     =      queue.pop(0				)
            if node == target:
                  lowercase_     =      (
                      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				)
                        lowercase_     =      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'''

import functools
from typing import Any


def __a (	__lowerCamelCase			:						str ,		__lowerCamelCase			:						list[str]				)	->							bool:
      '''simple docstring'''


      if not isinstance(__lowerCamelCase ,		__lowerCamelCase				) or len(__lowerCamelCase				) == 0:
            raise ValueError("the string should be not empty string"				)

      if not isinstance(__lowerCamelCase ,		__lowerCamelCase				) or not all(
          isinstance(__lowerCamelCase ,		__lowerCamelCase				) and len(__lowerCamelCase				) > 0 for item in words				):
            raise ValueError("the words should be a list of non-empty strings"				)

      # Build trie
      lowercase_     =      {}
      lowercase_     =      "WORD_KEEPER"

      for word in words:
            lowercase_     =      trie
            for c in word:
                  if c not in trie_node:
                        lowercase_     =      {}

                  lowercase_     =      trie_node[c]

            lowercase_     =      True

      lowercase_     =      len(__lowerCamelCase				)

      # Dynamic programming method
      @functools.cache
      def is_breakable(__lowerCamelCase			:						int				) -> bool:
            if index == len_string:
                  return True

            lowercase_     =      trie
            for i in range(__lowerCamelCase ,		__lowerCamelCase				):
                  lowercase_     =      trie_node.get(string[i] ,		__lowerCamelCase				)

                  if trie_node is None:
                        return False

                  if trie_node.get(__lowerCamelCase ,		__lowerCamelCase				) and is_breakable(i + 1				):
                        return True

            return False

      return is_breakable(0				)


if __name__ == "__main__":
       import doctest

       doctest.testmod()






