






"""simple docstring"""

lowercase    			=       {
    '''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:int ,						__lowerCamelCase:str   ):

						'''simple docstring'''






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

						'''simple docstring'''






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

						'''simple docstring'''






						return "".join(chr(ord(__lowerCamelCase   ) - 3_2   ) if "a" <= char <= "z" else char for char in word   )


if __name__ == "__main__":
			from doctest import testmod

			testmod()



