



'''simple docstring'''
snake_case_			:     Any  	=  {
    'A': ['B', 'C', 'E'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F', 'G'],
    'D': ['B'],
    'E': ['A', 'B', 'D'],
    'F': ['C'],
    'G': ['C'],
}






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

            # mark node as explored
																		explored.add(UpperCAmelCase_							)

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






def A__   (					UpperCAmelCase_  ,  UpperCAmelCase_  ,  UpperCAmelCase_							):
						if not graph or start not in graph or target not in graph:
												return -1
						if start == target:
												return 0
						_UpperCamelCase :		List[str]			    =       [start]
						_UpperCamelCase :		List[Any]			    =       set(UpperCAmelCase_							)
						# Keep tab on distances from `start` node.
						_UpperCamelCase :		int			    =       {start: 0, target: -1}
						while queue:
												_UpperCamelCase :		Union[str, Any]			    =       queue.pop(0							)
												if node == target:
																		_UpperCamelCase :		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(UpperCAmelCase_							)
																								queue.append(UpperCAmelCase_							)
																								_UpperCamelCase :		Any			    =       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'''
from __future__ import annotations

import numpy as np






def A__   (					UpperCAmelCase_							):
						_UpperCamelCase    ,      _UpperCamelCase :		Optional[int]			    =       np.shape(UpperCAmelCase_							)
						if rows != columns:
												_UpperCamelCase :		Union[str, Any]			    =       (
												    '\'table\' has to be of square shaped array but got a '
												    f'{rows}x{columns} array:\n{table}'
												)
												raise ValueError(UpperCAmelCase_							)

						_UpperCamelCase :		Optional[Any]			    =       np.zeros((rows, columns)							)
						_UpperCamelCase :		Tuple			    =       np.zeros((rows, columns)							)
						for i in range(UpperCAmelCase_							):
												for j in range(UpperCAmelCase_							):
																		_UpperCamelCase :		Optional[Any]			    =       sum(lower[i][k] * upper[k][j] for k in range(UpperCAmelCase_							)							)
																		if upper[j][j] == 0:
																								raise ArithmeticError('No LU decomposition exists'							)
																		_UpperCamelCase :		Optional[Any]			    =       (table[i][j] - total) / upper[j][j]
												_UpperCamelCase :		int			    =       1
												for j in range(UpperCAmelCase_  ,  UpperCAmelCase_							):
																		_UpperCamelCase :		Optional[int]			    =       sum(lower[i][k] * upper[k][j] for k in range(UpperCAmelCase_							)							)
																		_UpperCamelCase :		Tuple			    =       table[i][j] - total
						return lower, upper


if __name__ == "__main__":
					import doctest

					doctest.testmod()


