

'''simple docstring'''

SCREAMING_SNAKE_CASE							:				int     	=			{
    "A": ["B", "C", "E"],
    "B": ["A", "D", "E"],
    "C": ["A", "F", "G"],
    "D": ["B"],
    "E": ["A", "B", "D"],
    "F": ["C"],
    "G": ["C"],
}




def 							_UpperCamelCase				(   lowerCAmelCase__:					dict		,lowerCAmelCase__:					str		,lowerCAmelCase__:					int   )      -> list[str]:
							SCREAMING_SNAKE_CASE_				=				set()
							# keep track of all the paths to be checked
							SCREAMING_SNAKE_CASE_				=				[[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
														SCREAMING_SNAKE_CASE_				=				queue.pop(0   )
														# get the last node from the path
														SCREAMING_SNAKE_CASE_				=				path[-1]
														if node not in explored:
																					SCREAMING_SNAKE_CASE_				=				graph[node]
																					# go through all neighbour nodes, construct a new path and
																					# push it into the queue
																					for neighbour in neighbours:
																												SCREAMING_SNAKE_CASE_				=				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 							_UpperCamelCase				(   lowerCAmelCase__:					dict		,lowerCAmelCase__:					int		,lowerCAmelCase__:					List[Any]   )      -> int:
							if not graph or start not in graph or target not in graph:
														return -1
							if start == target:
														return 0
							SCREAMING_SNAKE_CASE_				=				[start]
							SCREAMING_SNAKE_CASE_				=				set(lowerCAmelCase__   )
							# Keep tab on distances from `start` node.
							SCREAMING_SNAKE_CASE_				=				{start: 0, target: -1}
							while queue:
														SCREAMING_SNAKE_CASE_				=				queue.pop(0   )
														if node == target:
																					SCREAMING_SNAKE_CASE_				=				(
																					    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__   )
																												SCREAMING_SNAKE_CASE_				=				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				(   lowerCAmelCase__:					int		,lowerCAmelCase__:					int   )      -> str:
							if a < 0 or b < 0:
														raise ValueError('the value of both inputs must be positive'   )
							SCREAMING_SNAKE_CASE_				=				str(bin(lowerCAmelCase__   )   )[2:]  # remove the leading "0b"
							SCREAMING_SNAKE_CASE_				=				str(bin(lowerCAmelCase__   )   )[2:]
							SCREAMING_SNAKE_CASE_				=				max(len(lowerCAmelCase__   )		,len(lowerCAmelCase__   )   )
							return "0b" + "".join(
							    str(int('1' in (char_a, char_b)   )   )
							    for char_a, char_b in zip(a_binary.zfill(lowerCAmelCase__   )		,b_binary.zfill(lowerCAmelCase__   )   )   )


if __name__ == "__main__":
							import doctest

							doctest.testmod()





