

'''simple docstring'''



from __future__ import annotations

from sys import maxsize
from typing import Generic, TypeVar

UpperCAmelCase :       Tuple			   =     TypeVar('T')







def    a__       (  a__						):




     """simple docstring"""


     return (position - 1) // 2







def    a__       (  a__						):




     """simple docstring"""


     return (2 * position) + 1







def    a__       (  a__						):




     """simple docstring"""


     return (2 * position) + 2







class 						lowerCAmelCase__   (      Generic[T]					):



 """simple docstring"""



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


      """simple docstring"""




      __SCREAMING_SNAKE_CASE     =      []
      __SCREAMING_SNAKE_CASE     =      {}
      __SCREAMING_SNAKE_CASE     =      0
 def __len__(		self					:       Optional[int]			)  -> int:


      """simple docstring"""




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


      """simple docstring"""




      return str(self.heap			)
 def       UpperCAmelCase__		(		self					:       int			)  -> bool:


      """simple docstring"""




      return self.elements == 0
 def       UpperCAmelCase__		(		self					:       List[str]					,							__SCREAMING_SNAKE_CASE					:       T					,							__SCREAMING_SNAKE_CASE					:       int			)  -> None:


      """simple docstring"""




      self.heap.append((elem, weight)			)
      __SCREAMING_SNAKE_CASE     =      self.elements
      self.elements += 1
      self._bubble_up(__SCREAMING_SNAKE_CASE			)
 def       UpperCAmelCase__		(		self					:       Tuple			)  -> T:


      """simple docstring"""




      if self.elements > 1:
           self._swap_nodes(0					,							self.elements - 1			)
      __SCREAMING_SNAKE_CASE   ,			__SCREAMING_SNAKE_CASE     =      self.heap.pop()
      del self.position_map[elem]
      self.elements -= 1
      if self.elements > 0:
           __SCREAMING_SNAKE_CASE   ,			__SCREAMING_SNAKE_CASE     =      self.heap[0]
           self._bubble_down(__SCREAMING_SNAKE_CASE			)
      return elem
 def       UpperCAmelCase__		(		self					:       int					,							__SCREAMING_SNAKE_CASE					:       T					,							__SCREAMING_SNAKE_CASE					:       int			)  -> None:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE     =      self.position_map[elem]
      __SCREAMING_SNAKE_CASE     =      (elem, weight)
      if position > 0:
           __SCREAMING_SNAKE_CASE     =      get_parent_position(__SCREAMING_SNAKE_CASE			)
           __SCREAMING_SNAKE_CASE   ,			__SCREAMING_SNAKE_CASE     =      self.heap[parent_position]
           if parent_weight > weight:
                self._bubble_up(__SCREAMING_SNAKE_CASE			)
           else:
                self._bubble_down(__SCREAMING_SNAKE_CASE			)
      else:
           self._bubble_down(__SCREAMING_SNAKE_CASE			)
 def       UpperCAmelCase__		(		self					:       Tuple					,							__SCREAMING_SNAKE_CASE					:       T			)  -> None:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE     =      self.position_map[elem]
      if curr_pos == 0:
           return None
      __SCREAMING_SNAKE_CASE     =      get_parent_position(__SCREAMING_SNAKE_CASE			)
      __SCREAMING_SNAKE_CASE   ,			__SCREAMING_SNAKE_CASE     =      self.heap[curr_pos]
      __SCREAMING_SNAKE_CASE   ,			__SCREAMING_SNAKE_CASE     =      self.heap[parent_position]
      if parent_weight > weight:
           self._swap_nodes(__SCREAMING_SNAKE_CASE					,							__SCREAMING_SNAKE_CASE			)
           return self._bubble_up(__SCREAMING_SNAKE_CASE			)
      return None
 def       UpperCAmelCase__		(		self					:       int					,							__SCREAMING_SNAKE_CASE					:       T			)  -> None:


      """simple docstring"""




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


 def       UpperCAmelCase__		(		self					:       Any					,							__SCREAMING_SNAKE_CASE					:       int					,							__SCREAMING_SNAKE_CASE					:       int			)  -> None:


      """simple docstring"""




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







class 						lowerCAmelCase__   (      Generic[T]					):



 """simple docstring"""



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


      """simple docstring"""




      __SCREAMING_SNAKE_CASE     =      {}
      __SCREAMING_SNAKE_CASE     =      0
 def __repr__(		self					:       Tuple			)  -> str:


      """simple docstring"""




      return str(self.connections			)
 def __len__(		self					:       Union[str, Any]			)  -> int:


      """simple docstring"""




      return self.nodes
 def       UpperCAmelCase__		(		self					:       Tuple					,							__SCREAMING_SNAKE_CASE					:       T			)  -> None:


      """simple docstring"""




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


 def       UpperCAmelCase__		(		self					:       str					,							__SCREAMING_SNAKE_CASE					:       T					,							__SCREAMING_SNAKE_CASE					:       T					,							__SCREAMING_SNAKE_CASE					:       int			)  -> None:


      """simple docstring"""




      self.add_node(__SCREAMING_SNAKE_CASE			)
      self.add_node(__SCREAMING_SNAKE_CASE			)
      __SCREAMING_SNAKE_CASE     =      weight
      __SCREAMING_SNAKE_CASE     =      weight







def    a__       (  a__      ,    ):




     """simple docstring"""


     __SCREAMING_SNAKE_CASE     =      {node: maxsize for node in graph.connections}
     __SCREAMING_SNAKE_CASE     =      {node: None for node in graph.connections}

     __SCREAMING_SNAKE_CASE     =      MinPriorityQueue()
     for node, weight in dist.items():
          priority_queue.push(a__      ,    a__						)

     if priority_queue.is_empty():
          return dist, parent

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

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









'''simple docstring'''



from itertools import count







def    a__       (  a__ = 50						):




     """simple docstring"""


     __SCREAMING_SNAKE_CASE     =      [1] * min_block_length

     for n in count(a__						):
          fill_count_functions.append(1						)

          for block_length in range(a__      ,    n + 1						):
               for block_start in range(n - block_length						):
                    fill_count_functions[n] += fill_count_functions[
                        n - block_start - block_length - 1
                    ]

               fill_count_functions[n] += 1

          if fill_count_functions[n] > 1_00_00_00:
               break

     return n


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






