






'''simple docstring'''







UpperCamelCase    :      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		:			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		:			Union[str, Any]   ,    __lowerCAmelCase		:			List[str]						):
						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'''







from math import factorial

UpperCamelCase    :      dict[str, int]  			=		{str(digit): factorial(digit) for digit in range(10)}
def 						A__			(				__lowerCAmelCase		:			int						):
						if not isinstance(__lowerCAmelCase   ,    __lowerCAmelCase						):
												raise TypeError("""Parameter number must be int"""						)

						if number < 0:
												raise ValueError("""Parameter number must be greater than or equal to 0"""						)

						# Converts number in string to iterate on its digits and adds its factorial.
						return sum(DIGIT_FACTORIAL[digit] for digit in str(__lowerCAmelCase						)						)
def 						A__			(				__lowerCAmelCase		:			int = 60   ,    __lowerCAmelCase		:			int = 100_0000						):

						if not isinstance(__lowerCAmelCase   ,    __lowerCAmelCase						) or not isinstance(__lowerCAmelCase   ,    __lowerCAmelCase						):
												raise TypeError("""Parameters chain_length and number_limit must be int"""						)

						if chain_length <= 0 or number_limit <= 0:
												raise ValueError(
												    """Parameters chain_length and number_limit must be greater than 0"""						)

						# the counter for the chains with the exact desired length
						lowerCamelCase__         =  0
						# the cached sizes of the previous chains
						lowerCamelCase__         =  {}

						for start_chain_element in range(1   ,    __lowerCAmelCase						):
												# The temporary set will contain the elements of the chain
												lowerCamelCase__         =  set()
												lowerCamelCase__         =  0

												# Stop computing the chain when you find a cached size, a repeating item or the
												# length is greater then the desired one.
												lowerCamelCase__         =  start_chain_element
												while (
												    chain_element not in chain_sets_lengths
												    and chain_element not in chain_set
												    and chain_set_length <= chain_length
												):
																		chain_set.add(__lowerCAmelCase						)
																		chain_set_length += 1
																		lowerCamelCase__         =  digit_factorial_sum(__lowerCAmelCase						)

												if chain_element in chain_sets_lengths:
																		chain_set_length += chain_sets_lengths[chain_element]

												lowerCamelCase__         =  chain_set_length

												# If chain contains the exact amount of elements increase the counter
												if chain_set_length == chain_length:
																		chains_counter += 1

						return chains_counter


if __name__ == "__main__":
							import doctest

							doctest.testmod()
							print(F'{solution()}')

