






import math
import sys




class 	lowerCamelCase__				:






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


       """simple docstring"""






       lowerCamelCase_							:    Union[str, Any]							=     0
       lowerCamelCase_							:    List[str]							=     []
       lowerCamelCase_							:    Dict							=     {}  # To store the pos of node in array






      def      UpperCAmelCase_     (self					:    Optional[int]		)       ->   Tuple:


       """simple docstring"""






       return self.cur_size == 0






      def      UpperCAmelCase_     (self					:    str		,		_snake_case					:    int		)       ->   Optional[int]:


       """simple docstring"""






       lowerCamelCase_							:    Tuple							=     self.left(_snake_case		)
       lowerCamelCase_							:    int							=     self.right(_snake_case		)
       if lc < self.cur_size and self.array(_snake_case		)[0] < self.array(_snake_case		)[0]:
        lowerCamelCase_							:    Optional[int]							=     lc
       else:
        lowerCamelCase_							:    Tuple							=     idx
       if rc < self.cur_size and self.array(_snake_case		)[0] < self.array(_snake_case		)[0]:
        lowerCamelCase_							:    Dict							=     rc
       if smallest != idx:
        self.swap(_snake_case		,		_snake_case		)
        self.min_heapify(_snake_case		)






      def      UpperCAmelCase_     (self					:    str		,		_snake_case					:    Dict		)       ->   Optional[Any]:


       """simple docstring"""






       lowerCamelCase_							:    Dict							=     self.cur_size
       self.cur_size += 1
       self.array.append((sys.maxsize, tup[1])		)
       self.decrease_key((sys.maxsize, tup[1])		,		tup[0]		)






      def      UpperCAmelCase_     (self					:    Optional[int]		)       ->   Optional[Any]:


       """simple docstring"""






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






      def      UpperCAmelCase_     (self					:    Dict		,		_snake_case					:    Tuple		)       ->   Tuple:


       """simple docstring"""






       return 2 * i + 1






      def      UpperCAmelCase_     (self					:    List[str]		,		_snake_case					:    Optional[int]		)       ->   Union[str, Any]:


       """simple docstring"""






       return 2 * i + 2






      def      UpperCAmelCase_     (self					:    int		,		_snake_case					:    Optional[int]		)       ->   Union[str, Any]:


       """simple docstring"""






       return math.floor(i / 2		)






      def      UpperCAmelCase_     (self					:    str		,		_snake_case					:    Dict		,		_snake_case					:    Tuple		)       ->   str:


       """simple docstring"""






       lowerCamelCase_							:    Dict							=     j
       lowerCamelCase_							:    List[str]							=     i
       lowerCamelCase_							:    List[Any]							=     self.array[i]
       lowerCamelCase_							:    List[str]							=     self.array[j]
       lowerCamelCase_							:    int							=     temp






      def      UpperCAmelCase_     (self					:    List[Any]		,		_snake_case					:    int		,		_snake_case					:    List[Any]		)       ->   Optional[int]:


       """simple docstring"""






       lowerCamelCase_							:    int							=     self.pos[tup[1]]
       # assuming the new_d is atmost old_d
       lowerCamelCase_							:    Optional[int]							=     (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		)		)
        lowerCamelCase_							:    Optional[Any]							=     self.par(_snake_case		)




class 	lowerCamelCase__				:






      def __init__(self					:    List[Any]		,		_snake_case					:    Optional[Any]		)       ->   Dict:


       """simple docstring"""






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






      def      UpperCAmelCase_     (self					:    Any		,		_snake_case					:    Dict		,		_snake_case					:    str		,		_snake_case					:    List[str]		)       ->   Optional[Any]:


       """simple docstring"""






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

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






      def      UpperCAmelCase_     (self					:    List[str]		)       ->   Optional[int]:


       """simple docstring"""






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






      def      UpperCAmelCase_     (self					:    Tuple		,		_snake_case					:    Any		)       ->   int:


       """simple docstring"""






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

       while not q.is_empty():
        lowerCamelCase_							:    Union[str, Any]							=     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]:
         lowerCamelCase_							:    List[str]							=     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		)
          lowerCamelCase_							:    Tuple							=     new_dist
          lowerCamelCase_							:    Union[str, Any]							=     u

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






      def      UpperCAmelCase_     (self					:    int		,		_snake_case					:    Optional[Any]		)       ->   Any:


       """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      UpperCAmelCase_     (self					:    Any		,		_snake_case					:    Dict		,		_snake_case					:    int		)       ->   Tuple:


       """simple docstring"""






       lowerCamelCase_							:    Dict							=     []
       lowerCamelCase_							:    Union[str, Any]							=     0
       lowerCamelCase_							:    Union[str, 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
        lowerCamelCase_							:    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											=      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








from __future__ import annotations




def       _a   (							lowerCamelCase__				)  ->      list[int]:
 lowerCamelCase_							:    Any							=     [0] * max_one

 for i in range(0 ,			lowerCamelCase__				):
  lowerCamelCase_							:    Union[str, Any]							=     i

 for i in range(2 ,			lowerCamelCase__				):
  if totients[i] == i:
   for j in range(lowerCamelCase__ ,			lowerCamelCase__ ,			lowerCamelCase__				):
    totients[j] -= totients[j] // i

 return totients




def       _a   (							lowerCamelCase__ ,			lowerCamelCase__				)  ->      bool:
 return sorted(str(lowerCamelCase__				)				) == sorted(str(lowerCamelCase__				)				)




def       _a   (							lowerCamelCase__ = 10_00_00_00				)  ->      int:
 lowerCamelCase_							:    Tuple							=     1  # i
 lowerCamelCase_							:    Union[str, Any]							=     0  # φ(i)
 lowerCamelCase_							:    List[Any]							=     get_totients(max_n + 1				)

 for i in range(2 ,			max_n + 1				):
  lowerCamelCase_							:    Tuple							=     totients[i]

  if i * min_denominator < min_numerator * t and has_same_digits(lowerCamelCase__ ,			lowerCamelCase__				):
   lowerCamelCase_							:    str							=     i
   lowerCamelCase_							:    List[Any]							=     t

 return min_numerator


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