

import math







class        a__       :







  """simple docstring"""




  def __init__(			self    : Optional[Any]				,				UpperCAmelCase__    : Union[str, Any]=0		)					->List[Any]:  # a graph with Node 0,1,...,N-1
        """simple docstring"""







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


  def  _lowercase      (			self    : str				,				UpperCAmelCase__    : List[Any]				,				UpperCAmelCase__    : Union[str, Any]				,				UpperCAmelCase__    : List[str]		)					->int:
        """simple docstring"""







        SCREAMING_SNAKE_CASE :      Optional[Any]       =   w


  def  _lowercase      (			self    : Dict		)					->Union[str, Any]:
        """simple docstring"""







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




  def  _lowercase      (			self    : str				,				UpperCAmelCase__    : str				,				UpperCAmelCase__    : Tuple		)					->str:
        """simple docstring"""







        return self.dp[u][v]


if __name__ == "__main__":
  UpperCAmelCase__ :     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)







def 					__lowercase      (     _A			)     ->						str:
      SCREAMING_SNAKE_CASE :      Optional[Any]       =   """"""
      for ch in key:
            if ch == " " or ch not in key_no_dups and ch.isalpha():
                  key_no_dups += ch
      return key_no_dups






def 					__lowercase      (     _A			)     ->						dict[str, str]:
      SCREAMING_SNAKE_CASE :      int       =   [chr(i + 65			) for i in range(26			)]
      # Remove duplicate characters from key
      SCREAMING_SNAKE_CASE :      List[str]       =   remove_duplicates(key.upper()			)
      SCREAMING_SNAKE_CASE :      Dict       =   len(_A			)
      # First fill cipher with key characters
      SCREAMING_SNAKE_CASE :      int       =   {alphabet[i]: char for i, char in enumerate(_A			)}
      # Then map remaining characters in alphabet to
      # the alphabet from the beginning
      for i in range(len(_A			)						,    26			):
            SCREAMING_SNAKE_CASE :      List[Any]       =   alphabet[i - offset]
            # Ensure we are not mapping letters to letters previously mapped
            while char in key:
                  offset -= 1
                  SCREAMING_SNAKE_CASE :      str       =   alphabet[i - offset]
            SCREAMING_SNAKE_CASE :      List[Any]       =   char
      return cipher_alphabet






def 					__lowercase      (     _A						,    _A			)     ->						str:
      return "".join(cipher_map.get(_A						,    _A			) for ch in message.upper()			)






def 					__lowercase      (     _A						,    _A			)     ->						str:
      SCREAMING_SNAKE_CASE :      Optional[int]       =   {v: k for k, v in cipher_map.items()}
      return "".join(rev_cipher_map.get(_A						,    _A			) for ch in message.upper()			)






def 					__lowercase      (     )     ->						None:
      SCREAMING_SNAKE_CASE :      List[Any]       =   input("""Enter message to encode or decode: """			).strip()
      SCREAMING_SNAKE_CASE :      str       =   input("""Enter keyword: """			).strip()
      SCREAMING_SNAKE_CASE :      Dict       =   input("""Encipher or decipher? E/D:"""			).strip()[0].lower()
      try:
            SCREAMING_SNAKE_CASE :      int       =   {"""e""": encipher, """d""": decipher}[option]
      except KeyError:
            raise KeyError("""invalid input option"""			)
      SCREAMING_SNAKE_CASE :      Optional[int]       =   create_cipher_map(_A			)
      print(func(_A						,    _A			)			)


if __name__ == "__main__":
  import doctest

  doctest.testmod()
  main()




