





class 							_UpperCamelCase					:

       def __init__(		self: Dict		)       -> Tuple:




              """simple docstring"""


              UpperCamelCase_          =  0
              UpperCamelCase_          =  0
              UpperCamelCase_          =  {}

       def lowercase (		self: Optional[Any]					,   _SCREAMING_SNAKE_CASE: Tuple		)       -> Any:




              """simple docstring"""


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

       def lowercase (		self: Dict					,   _SCREAMING_SNAKE_CASE: Tuple					,   _SCREAMING_SNAKE_CASE: List[Any]					,   _SCREAMING_SNAKE_CASE: List[str]		)       -> Tuple:




              """simple docstring"""


              self.add_vertex(_SCREAMING_SNAKE_CASE		)
              self.add_vertex(_SCREAMING_SNAKE_CASE		)

              if head == tail:
                     return

              UpperCamelCase_          =  weight
              UpperCamelCase_          =  weight

       def lowercase (		self: List[Any]		)       -> List[Any]:




              """simple docstring"""


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

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

       def __str__(		self: int		)       -> str:




              """simple docstring"""


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

       def lowercase (		self: Any		)       -> Any:




              """simple docstring"""


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

       def lowercase (		self: Any		)       -> Tuple:




              """simple docstring"""


              return self.adjacency.keys()

       @staticmethod
       def lowercase (		_SCREAMING_SNAKE_CASE: int=None					,   _SCREAMING_SNAKE_CASE: Any=None		)       -> Tuple:




              """simple docstring"""


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



       class 							_UpperCamelCase					:

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




                     """simple docstring"""


                     UpperCamelCase_          =  {}
                     UpperCamelCase_          =  {}

              def __len__(		self: List[Any]		)       -> int:




                     """simple docstring"""


                     return len(self.parent		)

              def lowercase (		self: str					,   _SCREAMING_SNAKE_CASE: int		)       -> Optional[int]:




                     """simple docstring"""


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

                     UpperCamelCase_          =  item
                     UpperCamelCase_          =  0
                     return item

              def lowercase (		self: Tuple					,   _SCREAMING_SNAKE_CASE: List[str]		)       -> List[str]:




                     """simple docstring"""


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



              def lowercase (		self: Tuple					,   _SCREAMING_SNAKE_CASE: List[Any]					,   _SCREAMING_SNAKE_CASE: Dict		)       -> Any:




                     """simple docstring"""


                     UpperCamelCase_          =  self.find(_SCREAMING_SNAKE_CASE		)
                     UpperCamelCase_          =  self.find(_SCREAMING_SNAKE_CASE		)

                     if roota == roota:
                            return roota

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

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

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

       @staticmethod
       def lowercase (		_SCREAMING_SNAKE_CASE: List[Any]		)       -> str:




              """simple docstring"""


              UpperCamelCase_          =  graph.num_vertices

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

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

                                   if cheap_edge[seta] == -1 or cheap_edge[seta][2] > weight:
                                          UpperCamelCase_          =  [head, tail, weight]
                     for vertex in cheap_edge:
                            if cheap_edge[vertex] != -1:
                                   UpperCamelCase_       , UpperCamelCase_       , UpperCamelCase_          =  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]		)
                                          UpperCamelCase_          =  num_components - 1
              UpperCamelCase_          =  Graph.build(edges=_SCREAMING_SNAKE_CASE		)
              return mst








import random
from typing import Any




def  lowerCAmelCase_ (							UpperCamelCase_  )     ->		list[Any]:
       for _ in range(len(UpperCamelCase_  )  ):
              UpperCamelCase_          =  random.randint(0					,		len(UpperCamelCase_  ) - 1  )
              UpperCamelCase_          =  random.randint(0					,		len(UpperCamelCase_  ) - 1  )
              UpperCamelCase_       , UpperCamelCase_          =  data[b], data[a]
       return data


if __name__ == "__main__":
     _UpperCAmelCase        =				[0, 1, 2, 3, 4, 5, 6, 7]
     _UpperCAmelCase        =				['python', 'says', 'hello', '!']
     print('Fisher-Yates Shuffle:')
     print('List', integers, strings)
     print('FY Shuffle', fisher_yates_shuffle(integers), fisher_yates_shuffle(strings))

