




import math
import sys

class 			_lowerCamelCase    :

      """simple docstring"""

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







      def    snake_case						(  self       :			Any					):
          return self.cur_size == 0







      def    snake_case						(  self       :			Any			,							snake_case       :			Tuple					):
          __UpperCamelCase			=    self.left(snake_case					)
          __UpperCamelCase			=    self.right(snake_case					)
          if lc < self.cur_size and self.array(snake_case					)[0] < self.array(snake_case					)[0]:
              __UpperCamelCase			=    lc
          else:
              __UpperCamelCase			=    idx
          if rc < self.cur_size and self.array(snake_case					)[0] < self.array(snake_case					)[0]:
              __UpperCamelCase			=    rc
          if smallest != idx:
              self.swap(snake_case			,							snake_case					)
              self.min_heapify(snake_case					)







      def    snake_case						(  self       :			Dict			,							snake_case       :			Any					):
          # Inserts a node into the Priority Queue
          __UpperCamelCase			=    self.cur_size
          self.cur_size += 1
          self.array.append((sys.maxsize, tup[1])					)
          self.decrease_key((sys.maxsize, tup[1])			,							tup[0]					)







      def    snake_case						(  self       :			Dict					):
          # Removes and returns the min element at top of priority queue
          __UpperCamelCase			=    self.array[0][1]
          __UpperCamelCase			=    self.array[self.cur_size - 1]
          self.cur_size -= 1
          self.min_heapify(1					)
          del self.pos[min_node]
          return min_node







      def    snake_case						(  self       :			Any			,							snake_case       :			int					):
          # returns the index of left child
          return 2 * i + 1







      def    snake_case						(  self       :			str			,							snake_case       :			Dict					):
          # returns the index of right child
          return 2 * i + 2







      def    snake_case						(  self       :			Optional[Any]			,							snake_case       :			Union[str, Any]					):
          # returns the index of parent
          return math.floor(i / 2					)







      def    snake_case						(  self       :			Any			,							snake_case       :			Optional[Any]			,							snake_case       :			str					):
          # swaps array elements at indices i and j
          # update the pos{}
          __UpperCamelCase			=    j
          __UpperCamelCase			=    i
          __UpperCamelCase			=    self.array[i]
          __UpperCamelCase			=    self.array[j]
          __UpperCamelCase			=    temp







      def    snake_case						(  self       :			Dict			,							snake_case       :			Optional[int]			,							snake_case       :			List[Any]					):
          __UpperCamelCase			=    self.pos[tup[1]]
          # assuming the new_d is atmost old_d
          __UpperCamelCase			=    (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			=    self.par(snake_case					)







class 			_lowerCamelCase    :

      """simple docstring"""

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







      def    snake_case						(  self       :			str			,							snake_case       :			Optional[int]			,							snake_case       :			Union[str, Any]			,							snake_case       :			Optional[Any]					):
          #  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			=    [(v, w)]

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







      def    snake_case						(  self       :			Optional[int]					):
          # u -> v(w)
          for u in self.adjList:
              print(snake_case			,							'''->'''			,							''' -> '''.join(str(F"{v}({w})"					) for v, w in self.adjList[u]					)					)







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

          while not q.is_empty():
              __UpperCamelCase			=    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			=    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			=    new_dist
                      __UpperCamelCase			=    u

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







      def    snake_case						(  self       :			Optional[int]			,							snake_case       :			List[str]					):
          print(F"Distance from node: {src}"					)
          for u in range(self.num_nodes					):
              print(F"Node {u} has distance: {self.dist[u]}"					)







      def    snake_case						(  self       :			Dict			,							snake_case       :			Optional[int]			,							snake_case       :			Optional[Any]					):
          # To show the shortest path from src to dest
          # WARNING: Use it *after* calling dijkstra
          __UpperCamelCase			=    []
          __UpperCamelCase			=    0
          __UpperCamelCase			=    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			=    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__":
 a_ 		=  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'''
def 				__UpperCamelCase (					__UpperCAmelCase  :					float ,   __UpperCAmelCase  :					float ,   __UpperCAmelCase  :					float			)							->	list[int]:
  if hue < 0 or hue > 360:
    raise Exception('''hue should be between 0 and 360'''			)

  if saturation < 0 or saturation > 1:
    raise Exception('''saturation should be between 0 and 1'''			)

  if value < 0 or value > 1:
    raise Exception('''value should be between 0 and 1'''			)

  lowercase				:							List[str]									=   value * saturation
  lowercase				:							Optional[Any]									=   hue / 60
  lowercase				:							Dict									=   chroma * (1 - abs(hue_section % 2 - 1			))
  lowercase				:							List[Any]									=   value - chroma

  if hue_section >= 0 and hue_section <= 1:
    lowercase				:							Optional[int]									=   round(255 * (chroma + match_value)			)
    lowercase				:							List[Any]									=   round(255 * (second_largest_component + match_value)			)
    lowercase				:							int									=   round(255 * (match_value)			)
  elif hue_section > 1 and hue_section <= 2:
    lowercase				:							Optional[Any]									=   round(255 * (second_largest_component + match_value)			)
    lowercase				:							Any									=   round(255 * (chroma + match_value)			)
    lowercase				:							Any									=   round(255 * (match_value)			)
  elif hue_section > 2 and hue_section <= 3:
    lowercase				:							Dict									=   round(255 * (match_value)			)
    lowercase				:							Optional[int]									=   round(255 * (chroma + match_value)			)
    lowercase				:							List[str]									=   round(255 * (second_largest_component + match_value)			)
  elif hue_section > 3 and hue_section <= 4:
    lowercase				:							List[str]									=   round(255 * (match_value)			)
    lowercase				:							List[str]									=   round(255 * (second_largest_component + match_value)			)
    lowercase				:							Tuple									=   round(255 * (chroma + match_value)			)
  elif hue_section > 4 and hue_section <= 5:
    lowercase				:							Optional[int]									=   round(255 * (second_largest_component + match_value)			)
    lowercase				:							Tuple									=   round(255 * (match_value)			)
    lowercase				:							Optional[int]									=   round(255 * (chroma + match_value)			)
  else:
    lowercase				:							int									=   round(255 * (chroma + match_value)			)
    lowercase				:							Optional[Any]									=   round(255 * (match_value)			)
    lowercase				:							Optional[int]									=   round(255 * (second_largest_component + match_value)			)

  return [red, green, blue]







def 				__UpperCamelCase (					__UpperCAmelCase  :					int ,   __UpperCAmelCase  :					int ,   __UpperCAmelCase  :					int			)							->	list[float]:
  if red < 0 or red > 255:
    raise Exception('''red should be between 0 and 255'''			)

  if green < 0 or green > 255:
    raise Exception('''green should be between 0 and 255'''			)

  if blue < 0 or blue > 255:
    raise Exception('''blue should be between 0 and 255'''			)

  lowercase				:							str									=   red / 255
  lowercase				:							Union[str, Any]									=   green / 255
  lowercase				:							Union[str, Any]									=   blue / 255
  lowercase				:							str									=   max(__UpperCAmelCase ,   __UpperCAmelCase ,   __UpperCAmelCase			)
  lowercase				:							int									=   value - min(__UpperCAmelCase ,   __UpperCAmelCase ,   __UpperCAmelCase			)
  lowercase				:							Optional[int]									=   0 if value == 0 else chroma / value

  if chroma == 0:
    lowercase				:							Dict									=   0.0
  elif value == float_red:
    lowercase				:							Tuple									=   60 * (0 + (float_green - float_blue) / chroma)
  elif value == float_green:
    lowercase				:							Optional[int]									=   60 * (2 + (float_blue - float_red) / chroma)
  else:
    lowercase				:							Dict									=   60 * (4 + (float_red - float_green) / chroma)

  lowercase				:							List[str]									=   (hue + 360) % 360

  return [hue, saturation, value]







def 				__UpperCamelCase (					__UpperCAmelCase  :					list[float] ,   __UpperCAmelCase  :					list[float]			)							->	bool:
  lowercase				:							int									=   abs(hsv_a[0] - hsv_a[0]			) < 0.2
  lowercase				:							Optional[int]									=   abs(hsv_a[1] - hsv_a[1]			) < 0.002
  lowercase				:							Dict									=   abs(hsv_a[2] - hsv_a[2]			) < 0.002

  return check_hue and check_saturation and check_value