



"""simple docstring"""





class  lowercase__  :







       '''simple docstring'''


       def __init__(				self     :    Dict						,							_UpperCAmelCase     :    int						,							_UpperCAmelCase     :    Optional[Any]=None						,							_UpperCAmelCase     :    Optional[Any]=None       )					->		Dict:


             '''simple docstring'''




             UpperCAmelCase_     					=				data
             UpperCAmelCase_     					=				previous
             UpperCAmelCase_     					=				next_node



       def __str__(				self     :    int       )					->		str:


             '''simple docstring'''




             return F"""{self.data}"""



       def 	lowercase__							(				self     :    int       )					->		int:


             '''simple docstring'''




             return self.data



       def 	lowercase__							(				self     :    Tuple       )					->		Optional[int]:


             '''simple docstring'''




             return self.next







       def 	lowercase__							(				self     :    Optional[int]       )					->		Any:


             '''simple docstring'''




             return self.previous



class  lowercase__  :







       '''simple docstring'''


       def __init__(				self     :    Tuple						,							_UpperCAmelCase     :    Optional[Any]       )					->		str:


             '''simple docstring'''




             UpperCAmelCase_     					=				head



       def __iter__(				self     :    Union[str, Any]       )					->		List[Any]:


             '''simple docstring'''




             return self







       def 	lowercase__							(				self     :    str       )					->		str:


             '''simple docstring'''




             if not self.current:
                   raise StopIteration
             else:
                   UpperCAmelCase_     					=				self.current.get_data()
                   UpperCAmelCase_     					=				self.current.get_next()
                   return value



class  lowercase__  :







       '''simple docstring'''


       def __init__(				self     :    List[str]       )					->		Any:


             '''simple docstring'''




             UpperCAmelCase_     					=				None  # First node in list
             UpperCAmelCase_     					=				None  # Last node in list



       def __str__(				self     :    int       )					->		Any:


             '''simple docstring'''




             UpperCAmelCase_     					=				self.head
             UpperCAmelCase_     					=				[]
             while current is not None:
                   nodes.append(current.get_data()       )
                   UpperCAmelCase_     					=				current.get_next()
             return " ".join(str(__lowerCamelCase       ) for node in nodes       )



       def __contains__(				self     :    Tuple						,							_UpperCAmelCase     :    int       )					->		List[Any]:


             '''simple docstring'''




             UpperCAmelCase_     					=				self.head
             while current:
                   if current.get_data() == value:
                         return True
                   UpperCAmelCase_     					=				current.get_next()
             return False



       def __iter__(				self     :    Optional[int]       )					->		List[str]:


             '''simple docstring'''




             return LinkedListIterator(self.head       )



       def 	lowercase__							(				self     :    Any       )					->		str:


             '''simple docstring'''




             if self.head:
                   return self.head.get_data()
             return None



       def 	lowercase__							(				self     :    str       )					->		Union[str, Any]:


             '''simple docstring'''




             if self.tail:
                   return self.tail.get_data()
             return None



       def 	lowercase__							(				self     :    str						,							_UpperCAmelCase     :    Node       )					->		None:


             '''simple docstring'''




             if self.head is None:
                   UpperCAmelCase_     					=				node
                   UpperCAmelCase_     					=				node
             else:
                   self.insert_before_node(self.head						,							__lowerCamelCase       )



       def 	lowercase__							(				self     :    Dict						,							_UpperCAmelCase     :    Node       )					->		None:


             '''simple docstring'''




             if self.head is None:
                   self.set_head(__lowerCamelCase       )
             else:
                   self.insert_after_node(self.tail						,							__lowerCamelCase       )



       def 	lowercase__							(				self     :    Optional[Any]						,							_UpperCAmelCase     :    int       )					->		None:


             '''simple docstring'''




             UpperCAmelCase_     					=				Node(__lowerCamelCase       )
             if self.head is None:
                   self.set_head(__lowerCamelCase       )
             else:
                   self.set_tail(__lowerCamelCase       )



       def 	lowercase__							(				self     :    int						,							_UpperCAmelCase     :    Node						,							_UpperCAmelCase     :    Node       )					->		None:


             '''simple docstring'''




             UpperCAmelCase_     					=				node
             UpperCAmelCase_     					=				node.previous

             if node.get_previous() is None:
                   UpperCAmelCase_     					=				node_to_insert
             else:
                   UpperCAmelCase_     					=				node_to_insert

             UpperCAmelCase_     					=				node_to_insert



       def 	lowercase__							(				self     :    Optional[Any]						,							_UpperCAmelCase     :    Node						,							_UpperCAmelCase     :    Node       )					->		None:


             '''simple docstring'''




             UpperCAmelCase_     					=				node
             UpperCAmelCase_     					=				node.next

             if node.get_next() is None:
                   UpperCAmelCase_     					=				node_to_insert
             else:
                   UpperCAmelCase_     					=				node_to_insert

             UpperCAmelCase_     					=				node_to_insert



       def 	lowercase__							(				self     :    List[str]						,							_UpperCAmelCase     :    int						,							_UpperCAmelCase     :    int       )					->		None:


             '''simple docstring'''




             UpperCAmelCase_     					=				1
             UpperCAmelCase_     					=				Node(__lowerCamelCase       )
             UpperCAmelCase_     					=				self.head
             while node:
                   if current_position == position:
                         self.insert_before_node(__lowerCamelCase						,							__lowerCamelCase       )
                         return
                   current_position += 1
                   UpperCAmelCase_     					=				node.next
             self.insert_after_node(self.tail						,							__lowerCamelCase       )



       def 	lowercase__							(				self     :    Optional[Any]						,							_UpperCAmelCase     :    int       )					->		Node:


             '''simple docstring'''




             UpperCAmelCase_     					=				self.head
             while node:
                   if node.get_data() == item:
                         return node
                   UpperCAmelCase_     					=				node.get_next()
             raise Exception("Node not found"       )



       def 	lowercase__							(				self     :    Optional[Any]						,							_UpperCAmelCase     :    List[str]       )					->		Dict:


             '''simple docstring'''




             if (node := self.get_node(__lowerCamelCase       )) is not None:
                   if node == self.head:
                         UpperCAmelCase_     					=				self.head.get_next()

                   if node == self.tail:
                         UpperCAmelCase_     					=				self.tail.get_previous()

                   self.remove_node_pointers(__lowerCamelCase       )



       @staticmethod
       def 	lowercase__							(				_UpperCAmelCase     :    Node       )					->		None:


             '''simple docstring'''




             if node.get_next():
                   UpperCAmelCase_     					=				node.previous

             if node.get_previous():
                   UpperCAmelCase_     					=				node.next

             UpperCAmelCase_     					=				None
             UpperCAmelCase_     					=				None







       def 	lowercase__							(				self     :    str       )					->		List[str]:


             '''simple docstring'''




             return self.head is None



def   a__      ( ):
      pass


if __name__ == "__main__":
  import doctest

  doctest.testmod()











from __future__ import annotations

from sys import maxsize
from typing import Generic, TypeVar

SCREAMING_SNAKE_CASE_   :      Optional[int]			=   TypeVar('''T''')



def  SCREAMING_SNAKE_CASE				(      snake_case							)		->    int:
		return (position - 1) // 2



def  SCREAMING_SNAKE_CASE				(      snake_case							)		->    int:
		return (2 * position) + 1



def  SCREAMING_SNAKE_CASE				(      snake_case							)		->    int:
		return (2 * position) + 2

class 		snake_case_   (							Generic[T]						):







	'''simple docstring'''




	def __init__(						self							:     Any   )       -> None:

			'''simple docstring'''




			__lowercase											=     []
			__lowercase											=     {}
			__lowercase											=     0




	def __len__(						self							:     Optional[Any]   )       -> int:

			'''simple docstring'''




			return self.elements




	def __repr__(						self							:     Optional[Any]   )       -> str:

			'''simple docstring'''




			return str(self.heap   )




	def    UpperCAmelCase			(						self							:     Union[str, Any]   )       -> bool:

			'''simple docstring'''




			return self.elements == 0




	def    UpperCAmelCase			(						self							:     str					,      __lowerCamelCase							:     T					,      __lowerCamelCase							:     int   )       -> None:

			'''simple docstring'''




			self.heap.append((elem, weight)   )
			__lowercase											=     self.elements
			self.elements += 1
			self._bubble_up(__lowerCamelCase   )




	def    UpperCAmelCase			(						self							:     Dict   )       -> T:

			'''simple docstring'''




			if self.elements > 1:
					self._swap_nodes(0					,      self.elements - 1   )
			__lowercase						,      __lowercase											=     self.heap.pop()
			del self.position_map[elem]
			self.elements -= 1
			if self.elements > 0:
					__lowercase						,      __lowercase											=     self.heap[0]
					self._bubble_down(__lowerCamelCase   )
			return elem




	def    UpperCAmelCase			(						self							:     int					,      __lowerCamelCase							:     T					,      __lowerCamelCase							:     int   )       -> None:

			'''simple docstring'''




			__lowercase											=     self.position_map[elem]
			__lowercase											=     (elem, weight)
			if position > 0:
					__lowercase											=     get_parent_position(__lowerCamelCase   )
					__lowercase						,      __lowercase											=     self.heap[parent_position]
					if parent_weight > weight:
							self._bubble_up(__lowerCamelCase   )
					else:
							self._bubble_down(__lowerCamelCase   )
			else:
					self._bubble_down(__lowerCamelCase   )




	def    UpperCAmelCase			(						self							:     Tuple					,      __lowerCamelCase							:     T   )       -> None:

			'''simple docstring'''




			__lowercase											=     self.position_map[elem]
			if curr_pos == 0:
					return None
			__lowercase											=     get_parent_position(__lowerCamelCase   )
			__lowercase						,      __lowercase											=     self.heap[curr_pos]
			__lowercase						,      __lowercase											=     self.heap[parent_position]
			if parent_weight > weight:
					self._swap_nodes(__lowerCamelCase					,      __lowerCamelCase   )
					return self._bubble_up(__lowerCamelCase   )
			return None




	def    UpperCAmelCase			(						self							:     List[str]					,      __lowerCamelCase							:     T   )       -> None:

			'''simple docstring'''




			__lowercase											=     self.position_map[elem]
			__lowercase						,      __lowercase											=     self.heap[curr_pos]
			__lowercase											=     get_child_left_position(__lowerCamelCase   )
			__lowercase											=     get_child_right_position(__lowerCamelCase   )
			if child_left_position < self.elements and child_right_position < self.elements:
					__lowercase						,      __lowercase											=     self.heap[child_left_position]
					__lowercase						,      __lowercase											=     self.heap[child_right_position]
					if child_right_weight < child_left_weight and child_right_weight < weight:
							self._swap_nodes(__lowerCamelCase					,      __lowerCamelCase   )
							return self._bubble_down(__lowerCamelCase   )
			if child_left_position < self.elements:
					__lowercase						,      __lowercase											=     self.heap[child_left_position]
					if child_left_weight < weight:
							self._swap_nodes(__lowerCamelCase					,      __lowerCamelCase   )
							return self._bubble_down(__lowerCamelCase   )
			else:
					return None
			if child_right_position < self.elements:
					__lowercase						,      __lowercase											=     self.heap[child_right_position]
					if child_right_weight < weight:
							self._swap_nodes(__lowerCamelCase					,      __lowerCamelCase   )
							return self._bubble_down(__lowerCamelCase   )
			return None






	def    UpperCAmelCase			(						self							:     Optional[int]					,      __lowerCamelCase							:     int					,      __lowerCamelCase							:     int   )       -> None:

			'''simple docstring'''




			__lowercase											=     self.heap[nodea_pos][0]
			__lowercase											=     self.heap[nodea_pos][0]
			__lowercase						,      __lowercase											=     (
			    self.heap[nodea_pos],
			    self.heap[nodea_pos],
			)
			__lowercase											=     nodea_pos
			__lowercase											=     nodea_pos





class 		snake_case_   (							Generic[T]						):







	'''simple docstring'''




	def __init__(						self							:     Optional[Any]   )       -> None:

			'''simple docstring'''




			__lowercase											=     {}
			__lowercase											=     0




	def __repr__(						self							:     Union[str, Any]   )       -> str:

			'''simple docstring'''




			return str(self.connections   )




	def __len__(						self							:     int   )       -> int:

			'''simple docstring'''




			return self.nodes




	def    UpperCAmelCase			(						self							:     Optional[int]					,      __lowerCamelCase							:     T   )       -> None:

			'''simple docstring'''




			if node not in self.connections:
					__lowercase											=     {}
					self.nodes += 1






	def    UpperCAmelCase			(						self							:     List[Any]					,      __lowerCamelCase							:     T					,      __lowerCamelCase							:     T					,      __lowerCamelCase							:     int   )       -> None:

			'''simple docstring'''




			self.add_node(__lowerCamelCase   )
			self.add_node(__lowerCamelCase   )
			__lowercase											=     weight
			__lowercase											=     weight





def  SCREAMING_SNAKE_CASE				(      snake_case						,   )		->    tuple[dict[T, int], dict[T, T | None]]:
		__lowercase											=     {node: maxsize for node in graph.connections}
		__lowercase											=     {node: None for node in graph.connections}

		__lowercase											=     MinPriorityQueue()
		for node, weight in dist.items():
				priority_queue.push(snake_case						,   snake_case							)

		if priority_queue.is_empty():
				return dist, parent

		# initialization
		__lowercase											=     priority_queue.extract_min()
		__lowercase											=     0
		for neighbour in graph.connections[node]:
				if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
						__lowercase											=     dist[node] + graph.connections[node][neighbour]
						priority_queue.update_key(snake_case						,   dist[neighbour]							)
						__lowercase											=     node

    # running prim's algorithm
		while not priority_queue.is_empty():
				__lowercase											=     priority_queue.extract_min()
				for neighbour in graph.connections[node]:
						if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
								__lowercase											=     dist[node] + graph.connections[node][neighbour]
								priority_queue.update_key(snake_case						,   dist[neighbour]							)
								__lowercase											=     node
		return dist, parent




