


'''simple docstring'''

from queue import PriorityQueue
from typing import Any

import numpy as np





def __snake_case					(      UpperCAmelCase_						:						dict					,				UpperCAmelCase_						:						str					,				UpperCAmelCase_						:						set					,				UpperCAmelCase_						:						set					,				UpperCAmelCase_						:						dict					,				UpperCAmelCase_						:						dict					,				UpperCAmelCase_						:						PriorityQueue					,				UpperCAmelCase_						:						dict					,				UpperCAmelCase_						:						float | int					,				):
 for nxt, d in graph[v]:
  if nxt in visited_forward:
   continue
  lowerCamelCase_      =  cst_fwd.get(UpperCAmelCase_					,				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 __snake_case					(      UpperCAmelCase_						:						str					,				UpperCAmelCase_						:						str					,				UpperCAmelCase_						:						dict					,				UpperCAmelCase_						:						dict		):
 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(UpperCAmelCase_		)

  lowerCamelCase_ ,lowerCamelCase_      =  queue_backward.get()
  visited_backward.add(UpperCAmelCase_		)

  lowerCamelCase_      =  pass_and_relaxation(
      UpperCAmelCase_					,				UpperCAmelCase_					,				UpperCAmelCase_					,				UpperCAmelCase_					,				UpperCAmelCase_					,				UpperCAmelCase_					,				UpperCAmelCase_					,				UpperCAmelCase_					,				UpperCAmelCase_					,				)

  lowerCamelCase_      =  pass_and_relaxation(
      UpperCAmelCase_					,				UpperCAmelCase_					,				UpperCAmelCase_					,				UpperCAmelCase_					,				UpperCAmelCase_					,				UpperCAmelCase_					,				UpperCAmelCase_					,				UpperCAmelCase_					,				UpperCAmelCase_					,				)

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







'''simple docstring'''

from __future__ import annotations





def __snake_case					(      UpperCAmelCase_						:						int		):
 lowerCamelCase_      =  2
 lowerCamelCase_      =  []
 while i * i <= n:
  if n % i:
   i += 1
  else:
   n //= i
   factors.append(UpperCAmelCase_		)
 if n > 1:
  factors.append(UpperCAmelCase_		)
 return factors


if __name__ == "__main__":
     import doctest

     doctest.testmod()



