


UpperCAmelCase   :    List[Any]     =		{
    "A": ["B", "C", "E"],
    "B": ["A", "D", "E"],
    "C": ["A", "F", "G"],
    "D": ["B"],
    "E": ["A", "B", "D"],
    "F": ["C"],
    "G": ["C"],
}






def 	__lowerCamelCase						(							lowerCamelCase__		:						dict  ,							lowerCamelCase__		:						Tuple  ,							lowerCamelCase__		:						Optional[Any]      ):





			'''simple docstring'''




			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 	__lowerCamelCase						(							lowerCamelCase__		:						dict  ,							lowerCamelCase__		:						Optional[Any]  ,							lowerCamelCase__		:						Optional[int]      ):





			'''simple docstring'''




			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





UpperCAmelCase   :    Any     =		[0, 2, 4, 6, 8]
UpperCAmelCase   :    Optional[Any]     =		[1, 3, 5, 7, 9]






def 	__lowerCamelCase						(							lowerCamelCase__		:						int  ,							lowerCamelCase__		:						int  ,							lowerCamelCase__		:						list[int]  ,							lowerCamelCase__		:						int      ):





			'''simple docstring'''




			if remaining_length == 0:
						if digits[0] == 0 or digits[-1] == 0:
									return 0

						for i in range(length // 2 - 1  ,							-1  ,							-1      ):
									remainder += digits[i] + digits[length - i - 1]

									if remainder % 2 == 0:
												return 0

									remainder //= 10

						return 1

			if remaining_length == 1:
						if remainder % 2 == 0:
									return 0

						lowerCamelCase    		=  0
						for digit in range(10      ):
									lowerCamelCase    		=  digit
									result += reversible_numbers(
									    0  ,							(remainder + 2 * digit) // 10  ,							lowerCamelCase__  ,							lowerCamelCase__      )
						return result

			lowerCamelCase    		=  0
			for digita in range(10      ):
						lowerCamelCase    		=  digita

						if (remainder + digita) % 2 == 0:
									lowerCamelCase    		=  ODD_DIGITS
						else:
									lowerCamelCase    		=  EVEN_DIGITS

						for digita in other_parity_digits:
									lowerCamelCase    		=  digita
									result += reversible_numbers(
									    remaining_length - 2  ,							(remainder + digita + digita) // 10  ,							lowerCamelCase__  ,							lowerCamelCase__  ,							)
			return result






def 	__lowerCamelCase						(							lowerCamelCase__		:						int = 9      ):





			'''simple docstring'''




			lowerCamelCase    		=  0
			for length in range(1  ,							max_power + 1      ):
						result += reversible_numbers(lowerCamelCase__  ,							0  ,							[0] * length  ,							lowerCamelCase__      )
			return result


if __name__ == "__main__":
		print(f"""{solution() = }""")

