






"""simple docstring"""



class 							__SCREAMING_SNAKE_CASE						:


       def __init__(			self      :						Optional[int]							):
             '''simple docstring'''





             A__						:  str		  =  0
             A__						:  List[str]		  =  0
             A__						:  Dict		  =  {}


       def 						_UpperCamelCase       (			self      :						str			,    snake_case      :						Tuple							):
             '''simple docstring'''





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


       def 						_UpperCamelCase       (			self      :						Dict			,    snake_case      :						str			,    snake_case      :						int			,    snake_case      :						Union[str, Any]							):
             '''simple docstring'''





             self.add_vertex(snake_case_							)
             self.add_vertex(snake_case_							)

             if head == tail:
                   return

             A__						:  Dict		  =  weight
             A__						:  str		  =  weight


       def 						_UpperCamelCase       (			self      :						str							):
             '''simple docstring'''





             A__						:  List[Any]		  =  self.get_edges()
             for edge in edges:
                   A__  ,  A__  ,  A__						:  Dict		  =  edge
                   edges.remove((tail, head, weight)							)
             for i in range(len(snake_case_							)							):
                   A__						:  int		  =  list(edges[i]							)

             edges.sort(key=lambda snake_case							: e[2]							)
             for i in range(len(snake_case_							) - 1							):
                   if edges[i][2] >= edges[i + 1][2]:
                         A__						:  Optional[int]		  =  edges[i][2] + 1
             for edge in edges:
                   A__  ,  A__  ,  A__						:  Any		  =  edge
                   A__						:  Optional[Any]		  =  weight
                   A__						:  Optional[int]		  =  weight


       def __str__(			self      :						Optional[int]							):
             '''simple docstring'''





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


       def 						_UpperCamelCase       (			self      :						Union[str, Any]							):
             '''simple docstring'''





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


       def 						_UpperCamelCase       (			self      :						List[str]							):
             '''simple docstring'''





             return self.adjacency.keys()


       @staticmethod
       def 						_UpperCamelCase       (			snake_case      :						Optional[Any]=None			,    snake_case      :						Optional[int]=None							):
             '''simple docstring'''





             A__						:  Union[str, Any]		  =  Graph()
             if vertices is None:
                   A__						:  Union[str, Any]		  =  []
             if edges is None:
                   A__						:  Optional[int]		  =  []
             for vertex in vertices:
                   g.add_vertex(snake_case_							)
             for edge in edges:
                   g.add_edge(*snake_case_							)
             return g






       class 							__SCREAMING_SNAKE_CASE						:


              def __init__(			self      :						List[str]							):
                    '''simple docstring'''





                    A__						:  str		  =  {}
                    A__						:  Optional[Any]		  =  {}


              def __len__(			self      :						Dict							):
                    '''simple docstring'''





                    return len(self.parent							)


              def 						_UpperCamelCase       (			self      :						List[Any]			,    snake_case      :						Any							):
                    '''simple docstring'''





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

                    A__						:  int		  =  item
                    A__						:  Optional[int]		  =  0
                    return item


              def 						_UpperCamelCase       (			self      :						Union[str, Any]			,    snake_case      :						Union[str, Any]							):
                    '''simple docstring'''





                    if item not in self.parent:
                          return self.make_set(snake_case_							)
                    if item != self.parent[item]:
                          A__						:  int		  =  self.find(self.parent[item]							)
                    return self.parent[item]


              def 						_UpperCamelCase       (			self      :						Optional[Any]			,    snake_case      :						Tuple			,    snake_case      :						Optional[int]							):
                    '''simple docstring'''





                    A__						:  List[Any]		  =  self.find(snake_case_							)
                    A__						:  List[str]		  =  self.find(snake_case_							)

                    if roota == roota:
                          return roota

                    if self.rank[roota] > self.rank[roota]:
                          A__						:  str		  =  roota
                          return roota

                    if self.rank[roota] < self.rank[roota]:
                          A__						:  int		  =  roota
                          return roota

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




       @staticmethod
       def 						_UpperCamelCase       (			snake_case      :						int							):
             '''simple docstring'''





             A__						:  Any		  =  graph.num_vertices

             A__						:  Optional[Any]		  =  Graph.UnionFind()
             A__						:  List[Any]		  =  []
             while num_components > 1:
                   A__						:  Optional[int]		  =  {}
                   for vertex in graph.get_vertices():
                         A__						:  List[Any]		  =  -1

                   A__						:  List[str]		  =  graph.get_edges()
                   for edge in edges:
                         A__  ,  A__  ,  A__						:  Optional[Any]		  =  edge
                         edges.remove((tail, head, weight)							)
                   for edge in edges:
                         A__  ,  A__  ,  A__						:  List[Any]		  =  edge
                         A__						:  List[Any]		  =  union_find.find(snake_case_							)
                         A__						:  str		  =  union_find.find(snake_case_							)
                         if seta != seta:
                               if cheap_edge[seta] == -1 or cheap_edge[seta][2] > weight:
                                     A__						:  Optional[Any]		  =  [head, tail, weight]

                               if cheap_edge[seta] == -1 or cheap_edge[seta][2] > weight:
                                     A__						:  List[Any]		  =  [head, tail, weight]
                   for vertex in cheap_edge:
                         if cheap_edge[vertex] != -1:
                               A__  ,  A__  ,  A__						:  Union[str, Any]		  =  cheap_edge[vertex]
                               if union_find.find(snake_case_							) != union_find.find(snake_case_							):
                                     union_find.union(snake_case_			,    snake_case_							)
                                     mst_edges.append(cheap_edge[vertex]							)
                                     A__						:  int		  =  num_components - 1
             A__						:  Tuple		  =  Graph.build(edges=snake_case_							)
             return mst














"""simple docstring"""



from __future__ import annotations

A_    =							10




def      _lowerCAmelCase		(							UpperCAmelCase__       :					list[int]      )		->list[int]:
						A__						:  Any		  =  1
						A__						:  Optional[int]		  =  max(UpperCAmelCase__      )
						while placement <= max_digit:
												# declare and initialize empty buckets
												A__						:  list[list]		  =  [[] for _ in range(UpperCAmelCase__      )]
												# split list_of_ints between the buckets
												for i in list_of_ints:
																		A__						:  List[Any]		  =  int((i / placement) % RADIX      )
																		buckets[tmp].append(UpperCAmelCase__      )
												# put each buckets' contents into list_of_ints
												A__						:  Union[str, Any]		  =  0
												for b in range(UpperCAmelCase__      ):
																		for i in buckets[b]:
																								A__						:  str		  =  i
																								a += 1
        # move to next
												placement *= RADIX
						return list_of_ints


if __name__ == "__main__":
						import doctest

						doctest.testmod()






