






from heapq import heappop, heappush

import numpy as np

def        __lowerCamelCase			(		snake_case__       ,snake_case__       ,snake_case__       ,snake_case__       ,)							->  tuple[float | int, list[tuple[int, int]]]:






						"""simple docstring"""





						_SCREAMING_SNAKE_CASE      ,     _SCREAMING_SNAKE_CASE	      =  grid.shape
						_SCREAMING_SNAKE_CASE	      =  [-1, 1, 0, 0]
						_SCREAMING_SNAKE_CASE	      =  [0, 0, -1, 1]
						if allow_diagonal:
												dx += [-1, -1, 1, 1]
												dy += [-1, 1, -1, 1]

						_SCREAMING_SNAKE_CASE      ,     _SCREAMING_SNAKE_CASE	      =  [(0, source)], set()
						_SCREAMING_SNAKE_CASE	      =  np.full((rows, cols)       ,np.inf		)
						_SCREAMING_SNAKE_CASE	      =  0
						_SCREAMING_SNAKE_CASE	      =  np.empty((rows, cols)       ,dtype=__lowerCAmelCase		)
						_SCREAMING_SNAKE_CASE	      =  None

						while queue:
												((_SCREAMING_SNAKE_CASE)      ,     (_SCREAMING_SNAKE_CASE))	      =  heappop(__lowerCAmelCase		)
												if (x, y) in visited:
																		continue
												visited.add((x, y)		)

												if (x, y) == destination:
																		_SCREAMING_SNAKE_CASE	      =  []
																		while (x, y) != source:
																								path.append((x, y)		)
																								_SCREAMING_SNAKE_CASE      ,     _SCREAMING_SNAKE_CASE	      =  predecessors[x, y]
																		path.append(__lowerCAmelCase		)  # add the source manually
																		path.reverse()
																		return matrix[destination], path

												for i in range(len(__lowerCAmelCase		)		):
																		_SCREAMING_SNAKE_CASE      ,     _SCREAMING_SNAKE_CASE	      =  x + dx[i], y + dy[i]
																		if 0 <= nx < rows and 0 <= ny < cols:
																								_SCREAMING_SNAKE_CASE	      =  grid[nx][ny]
																								if next_node == 1 and matrix[nx, ny] > dist + 1:
																														heappush(__lowerCAmelCase       ,(dist + 1, (nx, ny))		)
																														_SCREAMING_SNAKE_CASE	      =  dist + 1
																														_SCREAMING_SNAKE_CASE	      =  (x, y)

						return np.inf, []


if __name__ == "__main__":
		import doctest

		doctest.testmod()



from queue import PriorityQueue
from typing import Any

import numpy as np




def  __magic_name__ (   __lowerCAmelCase	:						dict		,  __lowerCAmelCase	:						str		,  __lowerCAmelCase	:						set		,  __lowerCAmelCase	:						set		,  __lowerCAmelCase	:						dict		,  __lowerCAmelCase	:						dict		,  __lowerCAmelCase	:						PriorityQueue		,  __lowerCAmelCase	:						dict		,  __lowerCAmelCase	:						float | int		,  )			->   float | int:
				for nxt, d in graph[v]:
								if nxt in visited_forward:
												continue
								__lowerCamelCase    					=	cst_fwd.get(__lowerCAmelCase		,  np.inf							)
								__lowerCamelCase    					=	cst_fwd[v] + d
								if new_cost_f < old_cost_f:
												queue.put((new_cost_f, nxt)							)
												__lowerCamelCase    					=	new_cost_f
												__lowerCamelCase    					=	v
								if nxt in visited_backward:
												if cst_fwd[v] + d + cst_bwd[nxt] < shortest_distance:
																__lowerCamelCase    					=	cst_fwd[v] + d + cst_bwd[nxt]
				return shortest_distance




def  __magic_name__ (   __lowerCAmelCase	:						str		,  __lowerCAmelCase	:						str		,  __lowerCAmelCase	:						dict		,  __lowerCAmelCase	:						dict							)			->   int:
				__lowerCamelCase    					=	-1

				__lowerCamelCase    					=	set()
				__lowerCamelCase    					=	set()
				__lowerCamelCase    					=	{source: 0}
				__lowerCamelCase    					=	{destination: 0}
				__lowerCamelCase    					=	{source: None}
				__lowerCamelCase    					=	{destination: None}
				__lowerCamelCase    					=	PriorityQueue()
				__lowerCamelCase    					=	PriorityQueue()

				__lowerCamelCase    					=	np.inf

				queue_forward.put((0, source)							)
				queue_backward.put((0, destination)							)

				if source == destination:
								return 0

				while not queue_forward.empty() and not queue_backward.empty():
								__lowerCamelCase					,    __lowerCamelCase    					=	queue_forward.get()
								visited_forward.add(__lowerCAmelCase							)

								__lowerCamelCase					,    __lowerCamelCase    					=	queue_backward.get()
								visited_backward.add(__lowerCAmelCase							)

								__lowerCamelCase    					=	pass_and_relaxation(
								    __lowerCAmelCase		,  __lowerCAmelCase		,  __lowerCAmelCase		,  __lowerCAmelCase		,  __lowerCAmelCase		,  __lowerCAmelCase		,  __lowerCAmelCase		,  __lowerCAmelCase		,  __lowerCAmelCase		,  )

								__lowerCamelCase    					=	pass_and_relaxation(
								    __lowerCAmelCase		,  __lowerCAmelCase		,  __lowerCAmelCase		,  __lowerCAmelCase		,  __lowerCAmelCase		,  __lowerCAmelCase		,  __lowerCAmelCase		,  __lowerCAmelCase		,  __lowerCAmelCase		,  )

								if cst_fwd[v_fwd] + cst_bwd[v_bwd] >= shortest_distance:
												break

				if shortest_distance != np.inf:
								__lowerCamelCase    					=	shortest_distance
				return shortest_path_distance


SCREAMING_SNAKE_CASE__   :			List[Any]												=    {
    "B": [["C", 1]],
    "C": [["D", 1]],
    "D": [["F", 1]],
    "E": [["B", 1], ["G", 2]],
    "F": [],
    "G": [["F", 1]],
}
SCREAMING_SNAKE_CASE__   :			Optional[int]												=    {
    "B": [["E", 1]],
    "C": [["B", 1]],
    "D": [["C", 1]],
    "F": [["D", 1], ["G", 1]],
    "E": [[None, np.inf]],
    "G": [["E", 2]],
}

if __name__ == "__main__":
					import doctest

					doctest.testmod()



