






'''simple docstring'''




class   _UpperCAmelCase     :




   """simple docstring"""

   def __init__(						self					:      int						):





         '''simple docstring'''





         _A     	=      0
         _A     	=      0
         _A     	=      {}

   def 		lowerCAmelCase					(						self					:      str , __UpperCAmelCase					:      Any						):





         '''simple docstring'''





         if vertex not in self.adjacency:
               _A     	=      {}
               self.num_vertices += 1

   def 		lowerCAmelCase					(						self					:      Union[str, Any] , __UpperCAmelCase					:      str , __UpperCAmelCase					:      Any , __UpperCAmelCase					:      str						):





         '''simple docstring'''





         self.add_vertex(__SCREAMING_SNAKE_CASE						)
         self.add_vertex(__SCREAMING_SNAKE_CASE						)

         if head == tail:
               return

         _A     	=      weight
         _A     	=      weight

   def 		lowerCAmelCase					(						self					:      Optional[int]						):





         '''simple docstring'''





         _A     	=      self.get_edges()
         for edge in edges:
               _A	,      _A	,      _A     	=      edge
               edges.remove((tail, head, weight)						)
         for i in range(len(__SCREAMING_SNAKE_CASE						)						):
               _A     	=      list(edges[i]						)

         edges.sort(key=lambda __UpperCAmelCase						: e[2]						)
         for i in range(len(__SCREAMING_SNAKE_CASE						) - 1						):
               if edges[i][2] >= edges[i + 1][2]:
                     _A     	=      edges[i][2] + 1
         for edge in edges:
               _A	,      _A	,      _A     	=      edge
               _A     	=      weight
               _A     	=      weight

   def __str__(						self					:      Any						):





         '''simple docstring'''





         _A     	=      ""
         for tail in self.adjacency:
               for head in self.adjacency[tail]:
                     _A     	=      self.adjacency[head][tail]
                     string += f'''{head} -> {tail} == {weight}\n'''
         return string.rstrip("\n"						)

   def 		lowerCAmelCase					(						self					:      Any						):





         '''simple docstring'''





         _A     	=      []
         for tail in self.adjacency:
               for head in self.adjacency[tail]:
                     output.append((tail, head, self.adjacency[head][tail])						)
         return output

   def 		lowerCAmelCase					(						self					:      Optional[int]						):





         '''simple docstring'''





         return self.adjacency.keys()

   @staticmethod
   def 		lowerCAmelCase					(						__UpperCAmelCase					:      List[Any]=None , __UpperCAmelCase					:      Optional[Any]=None						):





         '''simple docstring'''





         _A     	=      Graph()
         if vertices is None:
               _A     	=      []
         if edges is None:
               _A     	=      []
         for vertex in vertices:
               g.add_vertex(__SCREAMING_SNAKE_CASE						)
         for edge in edges:
               g.add_edge(*__SCREAMING_SNAKE_CASE						)
         return g

   class   _UpperCAmelCase     :




      """simple docstring"""

      def __init__(						self					:      List[str]						):





            '''simple docstring'''





            _A     	=      {}
            _A     	=      {}

      def __len__(						self					:      Dict						):





            '''simple docstring'''





            return len(self.parent						)

      def 		lowerCAmelCase					(						self					:      Tuple , __UpperCAmelCase					:      Dict						):





            '''simple docstring'''





            if item in self.parent:
                  return self.find(__SCREAMING_SNAKE_CASE						)

            _A     	=      item
            _A     	=      0
            return item

      def 		lowerCAmelCase					(						self					:      Tuple , __UpperCAmelCase					:      Optional[Any]						):





            '''simple docstring'''





            if item not in self.parent:
                  return self.make_set(__SCREAMING_SNAKE_CASE						)
            if item != self.parent[item]:
                  _A     	=      self.find(self.parent[item]						)
            return self.parent[item]

      def 		lowerCAmelCase					(						self					:      Optional[int] , __UpperCAmelCase					:      int , __UpperCAmelCase					:      int						):





            '''simple docstring'''





            _A     	=      self.find(__SCREAMING_SNAKE_CASE						)
            _A     	=      self.find(__SCREAMING_SNAKE_CASE						)

            if roota == roota:
                  return roota

            if self.rank[roota] > self.rank[roota]:
                  _A     	=      roota
                  return roota

            if self.rank[roota] < self.rank[roota]:
                  _A     	=      roota
                  return roota

            if self.rank[roota] == self.rank[roota]:
                  self.rank[roota] += 1
                  _A     	=      roota
                  return roota
            return None





   @staticmethod
   def 		lowerCAmelCase					(						__UpperCAmelCase					:      List[str]						):





         '''simple docstring'''





         _A     	=      graph.num_vertices

         _A     	=      Graph.UnionFind()
         _A     	=      []
         while num_components > 1:
               _A     	=      {}
               for vertex in graph.get_vertices():
                     _A     	=      -1

               _A     	=      graph.get_edges()
               for edge in edges:
                     _A	,      _A	,      _A     	=      edge
                     edges.remove((tail, head, weight)						)
               for edge in edges:
                     _A	,      _A	,      _A     	=      edge
                     _A     	=      union_find.find(__SCREAMING_SNAKE_CASE						)
                     _A     	=      union_find.find(__SCREAMING_SNAKE_CASE						)
                     if seta != seta:
                           if cheap_edge[seta] == -1 or cheap_edge[seta][2] > weight:
                                 _A     	=      [head, tail, weight]

                           if cheap_edge[seta] == -1 or cheap_edge[seta][2] > weight:
                                 _A     	=      [head, tail, weight]
               for vertex in cheap_edge:
                     if cheap_edge[vertex] != -1:
                           _A	,      _A	,      _A     	=      cheap_edge[vertex]
                           if union_find.find(__SCREAMING_SNAKE_CASE						) != union_find.find(__SCREAMING_SNAKE_CASE						):
                                 union_find.union(__SCREAMING_SNAKE_CASE , __SCREAMING_SNAKE_CASE						)
                                 mst_edges.append(cheap_edge[vertex]						)
                                 _A     	=      num_components - 1
         _A     	=      Graph.build(edges=__SCREAMING_SNAKE_CASE						)
         return mst













"""simple docstring"""





def 	lowerCamelCase__			(				_lowerCamelCase			:						str					) ->							bool:
  lowerCamelCase_       	=		0
  for ch in input_str:
    lowerCamelCase_       	=		ord(_lowerCamelCase					)
    lowerCamelCase_       	=		pow(2						,							_lowerCamelCase					)

    # If we already turned on bit for current character's unicode
    if bitmap >> ch_unicode & 1 == 1:
      return False
    bitmap |= ch_bit_index_on
  return True


if __name__ == "__main__":
  import doctest

  doctest.testmod()




