


'''simple docstring'''



import math
import sys



class       a							:


     """simple docstring"""






     def __init__(							self	:						str     )		->				List[str]:
          __UpperCAmelCase      :					str    				=     0
          __UpperCAmelCase      :					Union[str, Any]    				=     []
          __UpperCAmelCase      :					Dict    				=     {}  # To store the pos of node in array

     def 					lowerCamelCase__					(							self	:						List[str]     )		->				Any:
          return self.cur_size == 0

     def 					lowerCamelCase__					(							self	:						Tuple				,					snake_case	:						Any     )		->				Optional[Any]:
          __UpperCAmelCase      :					List[str]    				=     self.left(snake_case     )
          __UpperCAmelCase      :					Dict    				=     self.right(snake_case     )
          if lc < self.cur_size and self.array(snake_case     )[0] < self.array(snake_case     )[0]:
               __UpperCAmelCase      :					Tuple    				=     lc
          else:
               __UpperCAmelCase      :					Union[str, Any]    				=     idx
          if rc < self.cur_size and self.array(snake_case     )[0] < self.array(snake_case     )[0]:
               __UpperCAmelCase      :					List[str]    				=     rc
          if smallest != idx:
               self.swap(snake_case				,					snake_case     )
               self.min_heapify(snake_case     )

     def 					lowerCamelCase__					(							self	:						Tuple				,					snake_case	:						Any     )		->				Optional[Any]:
          # Inserts a node into the Priority Queue
          __UpperCAmelCase      :					Union[str, Any]    				=     self.cur_size
          self.cur_size += 1
          self.array.append((sys.maxsize, tup[1])     )
          self.decrease_key((sys.maxsize, tup[1])				,					tup[0]     )

     def 					lowerCamelCase__					(							self	:						Optional[int]     )		->				List[str]:
          # Removes and returns the min element at top of priority queue
          __UpperCAmelCase      :					int    				=     self.array[0][1]
          __UpperCAmelCase      :					Tuple    				=     self.array[self.cur_size - 1]
          self.cur_size -= 1
          self.min_heapify(1     )
          del self.pos[min_node]
          return min_node

     def 					lowerCamelCase__					(							self	:						Union[str, Any]				,					snake_case	:						Tuple     )		->				Optional[Any]:
          # returns the index of left child
          return 2 * i + 1

     def 					lowerCamelCase__					(							self	:						List[Any]				,					snake_case	:						List[str]     )		->				Union[str, Any]:
          # returns the index of right child
          return 2 * i + 2

     def 					lowerCamelCase__					(							self	:						int				,					snake_case	:						str     )		->				List[Any]:
          # returns the index of parent
          return math.floor(i / 2     )

     def 					lowerCamelCase__					(							self	:						Optional[int]				,					snake_case	:						Tuple				,					snake_case	:						Dict     )		->				Dict:
          # swaps array elements at indices i and j
          # update the pos{}
          __UpperCAmelCase      :					int    				=     j
          __UpperCAmelCase      :					Dict    				=     i
          __UpperCAmelCase      :					str    				=     self.array[i]
          __UpperCAmelCase      :					Dict    				=     self.array[j]
          __UpperCAmelCase      :					List[Any]    				=     temp






     def 					lowerCamelCase__					(							self	:						Optional[Any]				,					snake_case	:						Union[str, Any]				,					snake_case	:						Optional[int]     )		->				List[Any]:
          __UpperCAmelCase      :					Optional[Any]    				=     self.pos[tup[1]]
          # assuming the new_d is atmost old_d
          __UpperCAmelCase      :					List[Any]    				=     (new_d, tup[1])
          while idx > 0 and self.array[self.par(snake_case     )][0] > self.array[idx][0]:
               self.swap(snake_case				,					self.par(snake_case     )     )
               __UpperCAmelCase      :					Optional[Any]    				=     self.par(snake_case     )



class       a							:


     """simple docstring"""






     def __init__(							self	:						Dict				,					snake_case	:						List[str]     )		->				int:
          __UpperCAmelCase      :					Tuple    				=     {}  # To store graph: u -> (v,w)
          __UpperCAmelCase      :					List[str]    				=     num  # Number of nodes in graph
          # To store the distance from source vertex
          __UpperCAmelCase      :					Optional[int]    				=     [0] * self.num_nodes
          __UpperCAmelCase      :					Any    				=     [-1] * self.num_nodes  # To store the path

     def 					lowerCamelCase__					(							self	:						List[str]				,					snake_case	:						Optional[Any]				,					snake_case	:						List[Any]				,					snake_case	:						Optional[int]     )		->				str:
          #  Edge going from node u to v and v to u with weight w
          # u (w)-> v, v (w) -> u
          # Check if u already in graph
          if u in self.adjList:
               self.adjList[u].append((v, w)     )
          else:
               __UpperCAmelCase      :					Tuple    				=     [(v, w)]

          # Assuming undirected graph
          if v in self.adjList:
               self.adjList[v].append((u, w)     )
          else:
               __UpperCAmelCase      :					str    				=     [(u, w)]

     def 					lowerCamelCase__					(							self	:						str     )		->				Tuple:
          # u -> v(w)
          for u in self.adjList:
               print(snake_case				,					'''->'''				,					''' -> '''.join(str(f'{v}({w})'     ) for v, w in self.adjList[u]     )     )

     def 					lowerCamelCase__					(							self	:						List[Any]				,					snake_case	:						str     )		->				Union[str, Any]:
          # Flush old junk values in par[]
          __UpperCAmelCase      :					Optional[Any]    				=     [-1] * self.num_nodes
          # src is the source node
          __UpperCAmelCase      :					Optional[int]    				=     0
          __UpperCAmelCase      :					Optional[Any]    				=     PriorityQueue()
          q.insert((0, src)     )  # (dist from src, node)
          for u in self.adjList:
               if u != src:
                    __UpperCAmelCase      :					Any    				=     sys.maxsize  # Infinity
                    __UpperCAmelCase      :					List[str]    				=     -1

          while not q.is_empty():
               __UpperCAmelCase      :					Optional[int]    				=     q.extract_min()  # Returns node with the min dist from source
               # Update the distance of all the neighbours of u and
               # if their prev dist was INFINITY then push them in Q
               for v, w in self.adjList[u]:
                    __UpperCAmelCase      :					Tuple    				=     self.dist[u] + w
                    if self.dist[v] > new_dist:
                         if self.dist[v] == sys.maxsize:
                              q.insert((new_dist, v)     )
                         else:
                              q.decrease_key((self.dist[v], v)				,					snake_case     )
                         __UpperCAmelCase      :					Optional[int]    				=     new_dist
                         __UpperCAmelCase      :					str    				=     u

        # Show the shortest distances from src
          self.show_distances(snake_case     )

     def 					lowerCamelCase__					(							self	:						List[Any]				,					snake_case	:						Union[str, Any]     )		->				Optional[int]:
          print(f'Distance from node: {src}'     )
          for u in range(self.num_nodes     ):
               print(f'Node {u} has distance: {self.dist[u]}'     )






     def 					lowerCamelCase__					(							self	:						List[str]				,					snake_case	:						Any				,					snake_case	:						Optional[Any]     )		->				int:
          # To show the shortest path from src to dest
          # WARNING: Use it *after* calling dijkstra
          __UpperCAmelCase      :					List[Any]    				=     []
          __UpperCAmelCase      :					int    				=     0
          __UpperCAmelCase      :					List[Any]    				=     dest
          # Backtracking from dest to src
          while self.par[temp] != -1:
               path.append(snake_case     )
               if temp != src:
                    for v, w in self.adjList[temp]:
                         if v == self.par[temp]:
                              cost += w
                              break
               __UpperCAmelCase      :					List[str]    				=     self.par[temp]
          path.append(snake_case     )
          path.reverse()

          print(f'----Path to reach {dest} from {src}----'     )
          for u in path:
               print(f'{u}'				,					end=''' '''     )
               if u != dest:
                    print('''-> '''				,					end=''''''     )

          print('''\nTotal cost of path: '''				,					snake_case     )


if __name__ == "__main__":
      __UpperCAmelCase     :Any												=  Graph(9)
      graph.add_edge(0, 1, 4)
      graph.add_edge(0, 7, 8)
      graph.add_edge(1, 2, 8)
      graph.add_edge(1, 7, 1_1)
      graph.add_edge(2, 3, 7)
      graph.add_edge(2, 8, 2)
      graph.add_edge(2, 5, 4)
      graph.add_edge(3, 4, 9)
      graph.add_edge(3, 5, 1_4)
      graph.add_edge(4, 5, 1_0)
      graph.add_edge(5, 6, 2)
      graph.add_edge(6, 7, 1)
      graph.add_edge(6, 8, 6)
      graph.add_edge(7, 8, 7)
      graph.show_graph()
      graph.dijkstra(0)
      graph.show_path(0, 4)

# OUTPUT
# 0 -> 1(4) -> 7(8)
# 1 -> 0(4) -> 2(8) -> 7(11)
# 7 -> 0(8) -> 1(11) -> 6(1) -> 8(7)
# 2 -> 1(8) -> 3(7) -> 8(2) -> 5(4)
# 3 -> 2(7) -> 4(9) -> 5(14)
# 8 -> 2(2) -> 6(6) -> 7(7)
# 5 -> 2(4) -> 3(14) -> 4(10) -> 6(2)
# 4 -> 3(9) -> 5(10)
# 6 -> 5(2) -> 7(1) -> 8(6)
# Distance from node: 0
# Node 0 has distance: 0
# Node 1 has distance: 4
# Node 2 has distance: 12
# Node 3 has distance: 19
# Node 4 has distance: 21
# Node 5 has distance: 11
# Node 6 has distance: 9
# Node 7 has distance: 8
# Node 8 has distance: 14
# ----Path to reach 4 from 0----
# 0 -> 7 -> 6 -> 5 -> 4
# Total cost of path:  21



'''simple docstring'''



import math
from decimal import Decimal, getcontext




def       _a      (		_lowercase   :      int = 4000000    ):





     '''simple docstring'''






     try:
          __UpperCAmelCase      :					List[str]    				=     int(_lowercase    )
     except (TypeError, ValueError):
          raise TypeError('''Parameter n must be int or castable to int.'''    )
     if n <= 0:
          raise ValueError('''Parameter n must be greater than or equal to one.'''    )
     __UpperCAmelCase      :					Tuple    				=     100
     __UpperCAmelCase      :					Optional[Any]    				=     (Decimal(5    ) ** Decimal(0.5    ) + 1) / Decimal(2    )

     __UpperCAmelCase      :					Tuple    				=     (math.floor(math.log(n * (phi + 2)     ,   _lowercase    ) - 1    ) // 3) * 3 + 2
     __UpperCAmelCase      :					List[Any]    				=     Decimal(round(phi ** Decimal(index + 1    )    )    ) / (phi + 2)
     __UpperCAmelCase      :					List[str]    				=     num // 2
     return int(_lowercase    )


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