'''simple docstring'''

import math


class 				_lowercase	:
      '''simple docstring'''


      def __init__(				self					,lowerCamelCase_=0							)			->			Dict:  # a graph with Node 0,1,...,N-1



         '''simple docstring'''



         UpperCAmelCase__							:				int   				=  n
         UpperCAmelCase__							:				List[str]   				=  [
             [math.inf for j in range(0					,lowerCamelCase_							)] for i in range(0					,lowerCamelCase_							)
         ]  # adjacency matrix for weight
         UpperCAmelCase__							:				Union[str, Any]   				=  [
             [math.inf for j in range(0					,lowerCamelCase_							)] for i in range(0					,lowerCamelCase_							)
         ]  # dp[i][j] stores minimum distance from i to j




      def 		lowerCAmelCase__					(				self					,lowerCamelCase_					,lowerCamelCase_					,lowerCamelCase_							)			->			Optional[int]:



         '''simple docstring'''



         UpperCAmelCase__							:				Union[str, Any]   				=  w




      def 		lowerCAmelCase__					(				self							)			->			Optional[Any]:



         '''simple docstring'''



         for k in range(0					,self.n							):
            for i in range(0					,self.n							):
               for j in range(0					,self.n							):
                  UpperCAmelCase__							:				int   				=  min(self.dp[i][j]					,self.dp[i][k] + self.dp[k][j]							)




      def 		lowerCAmelCase__					(				self					,lowerCamelCase_					,lowerCamelCase_							)			->			Any:



         '''simple docstring'''



         return self.dp[u][v]


if __name__ == "__main__":
  UpperCamelCase__     :	List[str]				=			Graph(5)
  graph.add_edge(0, 2, 9)
  graph.add_edge(0, 4, 10)
  graph.add_edge(1, 3, 5)
  graph.add_edge(2, 3, 7)
  graph.add_edge(3, 0, 10)
  graph.add_edge(3, 1, 2)
  graph.add_edge(3, 2, 1)
  graph.add_edge(3, 4, 6)
  graph.add_edge(4, 1, 3)
  graph.add_edge(4, 2, 4)
  graph.add_edge(4, 3, 9)
  graph.floyd_warshall()
  graph.show_min(1, 4)
  graph.show_min(0, 3)




'''simple docstring'''

import re







def __UpperCamelCase(   _A					:				str    ):
   '''simple docstring'''

   if len(re.findall('''[ATCG]'''  ,			_A    )    ) != len(_A    ):
      raise ValueError('''Invalid Strand'''    )

   return dna.translate(dna.maketrans('''ATCG'''  ,			'''TAGC'''    )    )


if __name__ == "__main__":
  import doctest

  doctest.testmod()




