"""simple docstring"""






from __future__ import annotations

from sys import maxsize
from typing import Generic, TypeVar

__lowerCAmelCase					: str        =TypeVar("""T""")


def     UpperCAmelCase__ (       lowerCAmelCase__  :Optional[Any]	)				->					int:
      '''simple docstring'''


      return (position - 1) // 2


def     UpperCAmelCase__ (       lowerCAmelCase__  :Optional[Any]	)				->					int:
      '''simple docstring'''


      return (2 * position) + 1


def     UpperCAmelCase__ (       lowerCAmelCase__  :Optional[int]	)				->					int:
      '''simple docstring'''


      return (2 * position) + 2







class 				_A		( Generic[T]			):

      def __init__(		self		):







            """simple docstring"""



            lowercase														=			[]
            lowercase														=			{}
            lowercase														=			0

      def __len__(		self		):







            """simple docstring"""



            return self.elements

      def __repr__(		self		):







            """simple docstring"""



            return str(self.heap		)

      def        A__ (		self		):







            """simple docstring"""



            return self.elements == 0

      def        A__ (		self	, __lowerCAmelCase	, __lowerCAmelCase		):







            """simple docstring"""



            self.heap.append((elem, weight)		)
            lowercase														=			self.elements
            self.elements += 1
            self._bubble_up(__lowerCAmelCase		)

      def        A__ (		self		):







            """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        A__ (		self	, __lowerCAmelCase	, __lowerCAmelCase		):







            """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        A__ (		self	, __lowerCAmelCase		):







            """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        A__ (		self	, __lowerCAmelCase		):







            """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        A__ (		self	, __lowerCAmelCase	, __lowerCAmelCase		):







            """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 				_A		( Generic[T]			):

      def __init__(		self		):







            """simple docstring"""



            lowercase														=			{}
            lowercase														=			0

      def __repr__(		self		):







            """simple docstring"""



            return str(self.connections		)

      def __len__(		self		):







            """simple docstring"""



            return self.nodes

      def        A__ (		self	, __lowerCAmelCase		):







            """simple docstring"""



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







      def        A__ (		self	, __lowerCAmelCase	, __lowerCAmelCase	, __lowerCAmelCase		):







            """simple docstring"""



            self.add_node(__lowerCAmelCase		)
            self.add_node(__lowerCAmelCase		)
            lowercase														=			weight
            lowercase														=			weight






def     UpperCAmelCase__ (       lowerCAmelCase__  :str      ,	)				->					tuple[dict[T, int], dict[T, T | None]]:
      '''simple docstring'''


      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(_SCREAMING_SNAKE_CASE      ,	_SCREAMING_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(_SCREAMING_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(_SCREAMING_SNAKE_CASE      ,	dist[neighbour]	)
                        lowercase														=			node
      return dist, parent




"""simple docstring"""






def     UpperCAmelCase__ (       lowerCAmelCase__  :int	)				->					bool:
      '''simple docstring'''


      lowercase														=			(1 + 2_4 * n) ** 0.5
      return ((1 + root) / 6) % 1 == 0


def     UpperCAmelCase__ (       lowerCAmelCase__  :int = 5_0_0_0	)				->					int:
      '''simple docstring'''


      lowercase														=			[(i * (3 * i - 1)) // 2 for i in range(1      ,	lowerCAmelCase__	)]
      for i, pentagonal_i in enumerate(lowerCAmelCase__	):
            for j in range(lowerCAmelCase__      ,	len(lowerCAmelCase__	)	):
                  lowercase														=			pentagonal_nums[j]
                  lowercase														=			pentagonal_i + pentagonal_j
                  lowercase														=			pentagonal_j - pentagonal_i
                  if is_pentagonal(lowerCAmelCase__	) and is_pentagonal(lowerCAmelCase__	):
                        return b

      return -1


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



