




from queue import PriorityQueue
from typing import Any

import numpy as np
def 					lowerCamelCase_    (    SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	):
			'''simple docstring'''
			for nxt, d in graph[v]:
						if nxt in visited_forward:
									continue
						SCREAMING_SNAKE_CASE           =					cst_fwd.get(SCREAMING_SNAKE_CASE					,	np.inf   )
						SCREAMING_SNAKE_CASE           =					cst_fwd[v] + d
						if new_cost_f < old_cost_f:
									queue.put((new_cost_f, nxt)   )
									SCREAMING_SNAKE_CASE           =					new_cost_f
									SCREAMING_SNAKE_CASE           =					v
						if nxt in visited_backward:
									if cst_fwd[v] + d + cst_bwd[nxt] < shortest_distance:
												SCREAMING_SNAKE_CASE           =					cst_fwd[v] + d + cst_bwd[nxt]
			return shortest_distance
def 					lowerCamelCase_    (    SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE   ):
			'''simple docstring'''
			SCREAMING_SNAKE_CASE           =					-1

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

			SCREAMING_SNAKE_CASE           =					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():
						SCREAMING_SNAKE_CASE     ,  SCREAMING_SNAKE_CASE           =					queue_forward.get()
						visited_forward.add(SCREAMING_SNAKE_CASE   )

						SCREAMING_SNAKE_CASE     ,  SCREAMING_SNAKE_CASE           =					queue_backward.get()
						visited_backward.add(SCREAMING_SNAKE_CASE   )

						SCREAMING_SNAKE_CASE           =					pass_and_relaxation(
						    SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	)

						SCREAMING_SNAKE_CASE           =					pass_and_relaxation(
						    SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	)

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

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


__A						:							Optional[Any]							=  {
    """B""": [["""C""", 1]],
    """C""": [["""D""", 1]],
    """D""": [["""F""", 1]],
    """E""": [["""B""", 1], ["""G""", 2]],
    """F""": [],
    """G""": [["""F""", 1]],
}
__A						:							List[Any]							=  {
    """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()












def 					lowerCamelCase_    (    SCREAMING_SNAKE_CASE   ):
			'''simple docstring'''
			if not all(char in """01""" for char in bin_string   ):
						raise ValueError("""Non-binary value was passed to the function"""   )
			if not bin_string:
						raise ValueError("""Empty string was passed to the function"""   )
			SCREAMING_SNAKE_CASE           =					""""""
			while len(SCREAMING_SNAKE_CASE   ) % 3 != 0:
						SCREAMING_SNAKE_CASE           =					"""0""" + bin_string
			SCREAMING_SNAKE_CASE           =					[
			    bin_string[index : index + 3]
			    for index in range(len(SCREAMING_SNAKE_CASE   )   )
			    if index % 3 == 0
			]
			for bin_group in bin_string_in_3_list:
						SCREAMING_SNAKE_CASE           =					0
						for index, val in enumerate(SCREAMING_SNAKE_CASE   ):
									oct_val += int(2 ** (2 - index) * int(SCREAMING_SNAKE_CASE   )   )
						oct_string += str(SCREAMING_SNAKE_CASE   )
			return oct_string


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

		testmod()






