


"""simple docstring"""




import math
import sys





class __snake_case		:







   """simple docstring"""




   def __init__(		self							:Optional[int]       ):
          _a          =				0
          _a          =				[]
          _a          =				{}  # To store the pos of node in array




   def SCREAMING_SNAKE_CASE_      (		self							:Tuple       ):
          return self.cur_size == 0




   def SCREAMING_SNAKE_CASE_      (		self							:Union[str, Any]				,  UpperCamelCase__							:int       ):
          _a          =				self.left(__SCREAMING_SNAKE_CASE       )
          _a          =				self.right(__SCREAMING_SNAKE_CASE       )
          if lc < self.cur_size and self.array(__SCREAMING_SNAKE_CASE       )[0] < self.array(__SCREAMING_SNAKE_CASE       )[0]:
                 _a          =				lc
          else:
                 _a          =				idx
          if rc < self.cur_size and self.array(__SCREAMING_SNAKE_CASE       )[0] < self.array(__SCREAMING_SNAKE_CASE       )[0]:
                 _a          =				rc
          if smallest != idx:
                 self.swap(__SCREAMING_SNAKE_CASE				,  __SCREAMING_SNAKE_CASE       )
                 self.min_heapify(__SCREAMING_SNAKE_CASE       )




   def SCREAMING_SNAKE_CASE_      (		self							:Tuple				,  UpperCamelCase__							:List[Any]       ):
          _a          =				self.cur_size
          self.cur_size += 1
          self.array.append((sys.maxsize, tup[1])       )
          self.decrease_key((sys.maxsize, tup[1])				,  tup[0]       )




   def SCREAMING_SNAKE_CASE_      (		self							:List[Any]       ):
          _a          =				self.array[0][1]
          _a          =				self.array[self.cur_size - 1]
          self.cur_size -= 1
          self.min_heapify(1       )
          del self.pos[min_node]
          return min_node




   def SCREAMING_SNAKE_CASE_      (		self							:List[str]				,  UpperCamelCase__							:List[str]       ):
          return 2 * i + 1




   def SCREAMING_SNAKE_CASE_      (		self							:List[Any]				,  UpperCamelCase__							:Dict       ):
          return 2 * i + 2




   def SCREAMING_SNAKE_CASE_      (		self							:List[str]				,  UpperCamelCase__							:Optional[int]       ):
          return math.floor(i / 2       )




   def SCREAMING_SNAKE_CASE_      (		self							:int				,  UpperCamelCase__							:Union[str, Any]				,  UpperCamelCase__							:Dict       ):
          _a          =				j
          _a          =				i
          _a          =				self.array[i]
          _a          =				self.array[j]
          _a          =				temp




   def SCREAMING_SNAKE_CASE_      (		self							:Tuple				,  UpperCamelCase__							:Optional[Any]				,  UpperCamelCase__							:Tuple       ):
          _a          =				self.pos[tup[1]]
          # assuming the new_d is atmost old_d
          _a          =				(new_d, tup[1])
          while idx > 0 and self.array[self.par(__SCREAMING_SNAKE_CASE       )][0] > self.array[idx][0]:
                 self.swap(__SCREAMING_SNAKE_CASE				,  self.par(__SCREAMING_SNAKE_CASE       )       )
                 _a          =				self.par(__SCREAMING_SNAKE_CASE       )






class __snake_case		:







   """simple docstring"""




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




   def SCREAMING_SNAKE_CASE_      (		self							:str				,  UpperCamelCase__							:List[str]				,  UpperCamelCase__							:Any				,  UpperCamelCase__							:List[str]       ):

          if u in self.adjList:
                 self.adjList[u].append((v, w)       )
          else:
                 _a          =				[(v, w)]

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




   def SCREAMING_SNAKE_CASE_      (		self							:Optional[int]       ):

          for u in self.adjList:
                 print(__SCREAMING_SNAKE_CASE				,  "->"				,  " -> ".join(str(f'{v}({w})'       ) for v, w in self.adjList[u]       )       )




   def SCREAMING_SNAKE_CASE_      (		self							:Optional[Any]				,  UpperCamelCase__							:List[str]       ):
          _a          =				[-1] * self.num_nodes
          # src is the source node
          _a          =				0
          _a          =				PriorityQueue()
          q.insert((0, src)       )  # (dist from src, node)
          for u in self.adjList:
                 if u != src:
                        _a          =				sys.maxsize  # Infinity
                        _a          =				-1

          while not q.is_empty():
                 _a          =				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]:
                        _a          =				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)				,  __SCREAMING_SNAKE_CASE       )
                               _a          =				new_dist
                               _a          =				u

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




   def SCREAMING_SNAKE_CASE_      (		self							:List[Any]				,  UpperCamelCase__							:str       ):
          print(f'Distance from node: {src}'       )
          for u in range(self.num_nodes       ):
                 print(f'Node {u} has distance: {self.dist[u]}'       )




   def SCREAMING_SNAKE_CASE_      (		self							:List[Any]				,  UpperCamelCase__							:List[Any]				,  UpperCamelCase__							:List[Any]       ):
          _a          =				[]
          _a          =				0
          _a          =				dest
          # Backtracking from dest to src
          while self.par[temp] != -1:
                 path.append(__SCREAMING_SNAKE_CASE       )
                 if temp != src:
                        for v, w in self.adjList[temp]:
                               if v == self.par[temp]:
                                      cost += w
                                      break
                 _a          =				self.par[temp]
          path.append(__SCREAMING_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: "				,  __SCREAMING_SNAKE_CASE       )


if __name__ == "__main__":
   __SCREAMING_SNAKE_CASE					=						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, 11)
   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, 14)
   graph.add_edge(4, 5, 10)
   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"""




from __future__ import annotations

__SCREAMING_SNAKE_CASE					=						[2, 1, 4, 5, 6, 0, 8, 9, 1, 2, 0, 6, 4, 2, 0, 6, 5, 3, 2, 7]





class __snake_case		:







   """simple docstring"""




   def __init__(		self							:Optional[Any]				,  UpperCamelCase__							:int       ):
          _a          =				-1
          _a          =				-1
          _a          =				[-1] * length
          _a          =				None
          _a          =				None




   def __repr__(		self							:Optional[Any]       ):
          return f'Node(min_value={self.minn} max_value={self.maxx})'






def 						__a      (  a					):





       """simple docstring"""







       _a          =				Node(len(a					)					)
       _a   , _a          =				min(a					), max(a					)
       # Leaf node case where the node contains only one unique value
       if root.minn == root.maxx:
              return root
       _a          =				(root.minn + root.maxx) // 2

       _a          =				[]
       _a          =				[]

       for index, num in enumerate(a					):
              if num <= pivot:
                     left_arr.append(a					)
              else:
                     right_arr.append(a					)
              _a          =				len(a					)
       _a          =				build_tree(a					)
       _a          =				build_tree(a					)
       return root



def 						__a      (  a,		a,		a					):





       """simple docstring"""







       if index < 0 or node is None:
              return 0
       # Leaf node cases
       if node.minn == node.maxx:
              return index + 1 if node.minn == num else 0
       _a          =				(node.minn + node.maxx) // 2
       if num <= pivot:
              # go the left subtree and map index to the left subtree
              return rank_till_index(node.left,		a,		node.map_left[index] - 1					)
       else:
              # go to the right subtree and map index to the right subtree
              return rank_till_index(node.right,		a,		index - node.map_left[index]					)



def 						__a      (  a,		a,		a,		a					):





       """simple docstring"""







       if start > end:
              return 0
       _a          =				rank_till_index(a,		a,		a					)
       _a          =				rank_till_index(a,		a,		start - 1					)
       return rank_till_end - rank_before_start



def 						__a      (  a,		a,		a,		a					):





       """simple docstring"""







       if index > (end - start) or start > end or node is None:
              return -1
       # Leaf node case
       if node.minn == node.maxx:
              return node.minn
       # Number of elements in the left subtree in interval [start, end]
       _a          =				node.map_left[end] - (
           node.map_left[start - 1] if start else 0
       )
       if num_elements_in_left_tree > index:
              return quantile(
                  node.left,		a,		(node.map_left[start - 1] if start else 0),		node.map_left[end] - 1,		)
       else:
              return quantile(
                  node.right,		index - num_elements_in_left_tree,		start - (node.map_left[start - 1] if start else 0),		end - node.map_left[end],		)



def 						__a      (  a,		a,		a,		a,		a					):





       """simple docstring"""







       if (
           start > end
           or node is None
           or start_num > end_num
           or node.minn > end_num
           or node.maxx < start_num
       ):
              return 0
       if start_num <= node.minn and node.maxx <= end_num:
              return end - start + 1
       _a          =				range_counting(
           node.left,		(node.map_left[start - 1] if start else 0),		node.map_left[end] - 1,		a,		a,		)
       _a          =				range_counting(
           node.right,		start - (node.map_left[start - 1] if start else 0),		end - node.map_left[end],		a,		a,		)
       return left + right


if __name__ == "__main__":
   import doctest

   doctest.testmod()
