






"""simple docstring"""







_lowerCAmelCase            =	{
    'A': ['B', 'C', 'E'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F', 'G'],
    'D': ['B'],
    'E': ['A', 'B', 'D'],
    'F': ['C'],
    'G': ['C'],
}


def      UpperCamelCase       ( _A  ,				_A  ,				_A )     ->       list[str]:
				lowercase    :      Optional[int]       = set()
				# keep track of all the paths to be checked
				lowercase    :      Any       = [[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    :      List[Any]       = queue.pop(0 )
								# get the last node from the path
								lowercase    :      Dict       = path[-1]
								if node not in explored:
												lowercase    :      Any       = graph[node]
												# go through all neighbour nodes, construct a new path and
												# push it into the queue
												for neighbour in neighbours:
																lowercase    :      Union[str, Any]       = list(_A )
																new_path.append(_A )
																queue.append(_A )
																# return path if neighbour is goal
																if neighbour == goal:
																				return new_path

            # mark node as explored
												explored.add(_A )

    # in case there's no path between the 2 nodes
				return []


def      UpperCamelCase       ( _A  ,				_A  ,				_A )     ->       int:
				if not graph or start not in graph or target not in graph:
								return -1
				if start == target:
								return 0
				lowercase    :      List[Any]       = [start]
				lowercase    :      Any       = set(_A )
				# Keep tab on distances from `start` node.
				lowercase    :      Tuple       = {start: 0, target: -1}
				while queue:
								lowercase    :      List[Any]       = queue.pop(0 )
								if node == target:
												lowercase    :      Union[str, Any]       = (
												    dist[node] if dist[target] == -1 else min(dist[target]  ,				dist[node] )
												)
								for adjacent in graph[node]:
												if adjacent not in visited:
																visited.add(_A )
																queue.append(_A )
																lowercase    :      int       = 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"""







def      UpperCamelCase       ( _A )     ->       int:
				lowercase    :      Dict       = 0
				while num > 0:
								digit_sum += num % 10
								num //= 10
				return digit_sum


def      UpperCamelCase       ( _A = 100 )     ->       int:
				lowercase    :      Union[str, Any]       = 1
				lowercase    :      Tuple       = 2

				for i in range(2  ,				max_n + 1 ):
								lowercase    :      Any       = pre_numerator
								lowercase    :      Dict       = 2 * i // 3 if i % 3 == 0 else 1
								lowercase    :      Optional[Any]       = cur_numerator
								lowercase    :      str       = e_cont * pre_numerator + temp

				return sum_digits(_A )


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