

"""simple docstring"""


__A						   =			{
    "Pillow": "Pillow<10.0.0",
    "accelerate": "accelerate>=0.20.3",
    "av": "av==9.2.0",
    "beautifulsoup4": "beautifulsoup4",
    "black": "black~=23.1",
    "codecarbon": "codecarbon==1.2.0",
    "cookiecutter": "cookiecutter==1.7.3",
    "dataclasses": "dataclasses",
    "datasets": "datasets!=2.5.0",
    "decord": "decord==0.6.0",
    "deepspeed": "deepspeed>=0.9.3",
    "diffusers": "diffusers",
    "dill": "dill<0.3.5",
    "evaluate": "evaluate>=0.2.0",
    "fairscale": "fairscale>0.3",
    "faiss-cpu": "faiss-cpu",
    "fastapi": "fastapi",
    "filelock": "filelock",
    "flax": "flax>=0.4.1,<=0.7.0",
    "ftfy": "ftfy",
    "fugashi": "fugashi>=1.0",
    "GitPython": "GitPython<3.1.19",
    "hf-doc-builder": "hf-doc-builder>=0.3.0",
    "huggingface-hub": "huggingface-hub>=0.14.1,<1.0",
    "importlib_metadata": "importlib_metadata",
    "ipadic": "ipadic>=1.0.0,<2.0",
    "isort": "isort>=5.5.4",
    "jax": "jax>=0.2.8,!=0.3.2,<=0.4.13",
    "jaxlib": "jaxlib>=0.1.65,<=0.4.13",
    "jieba": "jieba",
    "kenlm": "kenlm",
    "keras-nlp": "keras-nlp>=0.3.1",
    "librosa": "librosa",
    "nltk": "nltk",
    "natten": "natten>=0.14.6",
    "numpy": "numpy>=1.17",
    "onnxconverter-common": "onnxconverter-common",
    "onnxruntime-tools": "onnxruntime-tools>=1.4.2",
    "onnxruntime": "onnxruntime>=1.4.0",
    "opencv-python": "opencv-python",
    "optuna": "optuna",
    "optax": "optax>=0.0.8,<=0.1.4",
    "packaging": "packaging>=20.0",
    "parameterized": "parameterized",
    "phonemizer": "phonemizer",
    "protobuf": "protobuf",
    "psutil": "psutil",
    "pyyaml": "pyyaml>=5.1",
    "pydantic": "pydantic<2",
    "pytest": "pytest>=7.2.0",
    "pytest-timeout": "pytest-timeout",
    "pytest-xdist": "pytest-xdist",
    "python": "python>=3.8.0",
    "ray[tune]": "ray[tune]",
    "regex": "regex!=2019.12.17",
    "requests": "requests",
    "rhoknp": "rhoknp>=1.1.0,<1.3.1",
    "rjieba": "rjieba",
    "rouge-score": "rouge-score!=0.0.7,!=0.0.8,!=0.1,!=0.1.1",
    "ruff": "ruff>=0.0.241,<=0.0.259",
    "sacrebleu": "sacrebleu>=1.4.12,<2.0.0",
    "sacremoses": "sacremoses",
    "safetensors": "safetensors>=0.3.1",
    "sagemaker": "sagemaker>=2.31.0",
    "scikit-learn": "scikit-learn",
    "sentencepiece": "sentencepiece>=0.1.91,!=0.1.92",
    "sigopt": "sigopt",
    "starlette": "starlette",
    "sudachipy": "sudachipy>=0.6.6",
    "sudachidict_core": "sudachidict_core>=20220729",
    "tensorflow-cpu": "tensorflow-cpu>=2.6,<2.14",
    "tensorflow": "tensorflow>=2.6,<2.14",
    "tensorflow-text": "tensorflow-text<2.14",
    "tf2onnx": "tf2onnx",
    "timeout-decorator": "timeout-decorator",
    "timm": "timm",
    "tokenizers": "tokenizers>=0.11.1,!=0.11.3,<0.14",
    "torch": "torch>=1.9,!=1.12.0",
    "torchaudio": "torchaudio",
    "torchvision": "torchvision",
    "pyctcdecode": "pyctcdecode>=0.4.0",
    "tqdm": "tqdm>=4.27",
    "unidic": "unidic>=1.0.2",
    "unidic_lite": "unidic_lite>=1.0.7",
    "urllib3": "urllib3<2.0.0",
    "uvicorn": "uvicorn",
}





"""simple docstring"""


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






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

            # mark node as explored
						explored.add(__SCREAMING_SNAKE_CASE )

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






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


