





"""simple docstring"""


import math
import sys



class   lowercase_					:

       def __init__(      self  ):






        '''simple docstring'''

        snake_case__     				=					0
        snake_case__     				=					[]
        snake_case__     				=					{}  # To store the pos of node in array

       def 		_SCREAMING_SNAKE_CASE(      self  ):






        '''simple docstring'''

        return self.cur_size == 0

       def 		_SCREAMING_SNAKE_CASE(      self ,       __SCREAMING_SNAKE_CASE  ):






        '''simple docstring'''

        snake_case__     				=					self.left(UpperCAmelCase_  )
        snake_case__     				=					self.right(UpperCAmelCase_  )
        if lc < self.cur_size and self.array(UpperCAmelCase_  )[0] < self.array(UpperCAmelCase_  )[0]:
         snake_case__     				=					lc
        else:
         snake_case__     				=					idx
        if rc < self.cur_size and self.array(UpperCAmelCase_  )[0] < self.array(UpperCAmelCase_  )[0]:
         snake_case__     				=					rc
        if smallest != idx:
         self.swap(UpperCAmelCase_ ,       UpperCAmelCase_  )
         self.min_heapify(UpperCAmelCase_  )

       def 		_SCREAMING_SNAKE_CASE(      self ,       __SCREAMING_SNAKE_CASE  ):






        '''simple docstring'''

        snake_case__     				=					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  ):






        '''simple docstring'''

        snake_case__     				=					self.array[0][1]
        snake_case__     				=					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 ,       __SCREAMING_SNAKE_CASE  ):






        '''simple docstring'''

        return 2 * i + 1

       def 		_SCREAMING_SNAKE_CASE(      self ,       __SCREAMING_SNAKE_CASE  ):






        '''simple docstring'''

        return 2 * i + 2

       def 		_SCREAMING_SNAKE_CASE(      self ,       __SCREAMING_SNAKE_CASE  ):






        '''simple docstring'''

        return math.floor(i / 2  )

       def 		_SCREAMING_SNAKE_CASE(      self ,       __SCREAMING_SNAKE_CASE ,       __SCREAMING_SNAKE_CASE  ):






        '''simple docstring'''

        snake_case__     				=					j
        snake_case__     				=					i
        snake_case__     				=					self.array[i]
        snake_case__     				=					self.array[j]
        snake_case__     				=					temp

       def 		_SCREAMING_SNAKE_CASE(      self ,       __SCREAMING_SNAKE_CASE ,       __SCREAMING_SNAKE_CASE  ):






        '''simple docstring'''

        snake_case__     				=					self.pos[tup[1]]
        # assuming the new_d is atmost old_d
        snake_case__     				=					(new_d, tup[1])
        while idx > 0 and self.array[self.par(UpperCAmelCase_  )][0] > self.array[idx][0]:
         self.swap(UpperCAmelCase_ ,       self.par(UpperCAmelCase_  )  )
         snake_case__     				=					self.par(UpperCAmelCase_  )



class   lowercase_					:

       def __init__(      self ,       __SCREAMING_SNAKE_CASE  ):






        '''simple docstring'''

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

       def 		_SCREAMING_SNAKE_CASE(      self ,       __SCREAMING_SNAKE_CASE ,       __SCREAMING_SNAKE_CASE ,       __SCREAMING_SNAKE_CASE  ):






        '''simple docstring'''

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

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

       def 		_SCREAMING_SNAKE_CASE(      self  ):






        '''simple docstring'''

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

       def 		_SCREAMING_SNAKE_CASE(      self ,       __SCREAMING_SNAKE_CASE  ):






        '''simple docstring'''

        snake_case__     				=					[-1] * self.num_nodes
        # src is the source node
        snake_case__     				=					0
        snake_case__     				=					PriorityQueue()
        q.insert((0, src)  )  # (dist from src, node)
        for u in self.adjList:
         if u != src:
          snake_case__     				=					sys.maxsize  # Infinity
          snake_case__     				=					-1

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

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

       def 		_SCREAMING_SNAKE_CASE(      self ,       __SCREAMING_SNAKE_CASE  ):






        '''simple docstring'''

        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 ,       __SCREAMING_SNAKE_CASE ,       __SCREAMING_SNAKE_CASE  ):






        '''simple docstring'''

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


if __name__ == "__main__":
   a__       :  str       		=					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









import math
from timeit import timeit

def 			__lowerCamelCase     (						snake_case__						)				->    int:






						"""simple docstring"""





						_SCREAMING_SNAKE_CASE       =    0
						_SCREAMING_SNAKE_CASE       =    abs(snake_case__						)
						while True:
												_SCREAMING_SNAKE_CASE       =    n // 10
												digits += 1
												if n == 0:
																		break
						return digits

def 			__lowerCamelCase     (						snake_case__						)				->    int:






						"""simple docstring"""





						return 1 if n == 0 else math.floor(math.log(abs(snake_case__						)			,10						) + 1						)

def 			__lowerCamelCase     (						snake_case__						)				->    int:






						"""simple docstring"""





						return len(str(abs(snake_case__						)						)						)

def 			__lowerCamelCase     (						)				->    None:






						"""simple docstring"""





						from collections.abc import Callable

						def benchmark_a_function(snake_case__			,snake_case__						) -> None:
												_SCREAMING_SNAKE_CASE       =    F'{func.__name__}({value})'
												_SCREAMING_SNAKE_CASE       =    timeit(F'__main__.{call}'			,setup="""import __main__"""						)
												print(F'{call}: {func(snake_case__						)} -- {timing} seconds'						)

						for value in (26_21_44, 11_25_89_99_06_84_26_24, 1_26_76_50_60_02_28_22_94_01_49_67_03_20_53_76):
												for func in (num_digits, num_digits_fast, num_digits_faster):
																		benchmark_a_function(snake_case__			,snake_case__						)
												print()


if __name__ == "__main__":
		import doctest

		doctest.testmod()
		benchmark()

