





'''simple docstring'''





from queue import PriorityQueue
from typing import Any

import numpy as np





def    __UpperCamelCase      (    a,     a,     a,     a,     a,     a,     a,     a,     a,     ) ->float | int:
					for nxt, d in graph[v]:
										if nxt in visited_forward:
															continue
										lowerCamelCase__       =       cst_fwd.get(a,     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    __UpperCamelCase      (    a,     a,     a,     a) ->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(a)

										lowerCamelCase__    ,		lowerCamelCase__       =       queue_backward.get()
										visited_backward.add(a)

										lowerCamelCase__       =       pass_and_relaxation(
										    a,     a,     a,     a,     a,     a,     a,     a,     a,     )

										lowerCamelCase__       =       pass_and_relaxation(
										    a,     a,     a,     a,     a,     a,     a,     a,     a,     )

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

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


A_												=     {
    "B": [["C", 1]],
    "C": [["D", 1]],
    "D": [["F", 1]],
    "E": [["B", 1], ["G", 2]],
    "F": [],
    "G": [["F", 1]],
}
A_												=     {
    "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    __UpperCamelCase      (    a = 100) ->int:
					lowerCamelCase__       =       (n * (n + 1) // 2) ** 2
					lowerCamelCase__       =       n * (n + 1) * (2 * n + 1) // 6
					return sum_cubes - sum_squares


if __name__ == "__main__":
						print(f"""{solution() = }""")

