


class      lowerCAmelCase__       :




     '''simple docstring'''


     def __init__(						self)			->				str:
            _A      :       Any				    = 0
            _A      :       List[Any]				    = 0
            _A      :       Tuple				    = {}


     def  _lowerCamelCase (						self ,						__lowerCamelCase)			->				Optional[int]:






            if vertex not in self.adjacency:
                   _A      :       Union[str, Any]				    = {}
                   self.num_vertices += 1


     def  _lowerCamelCase (						self ,						__lowerCamelCase ,						__lowerCamelCase ,						__lowerCamelCase)			->				List[Any]:
            self.add_vertex(__lowerCamelCase)
            self.add_vertex(__lowerCamelCase)

            if head == tail:
                   return

            _A      :       str				    = weight
            _A      :       str				    = weight


     def  _lowerCamelCase (						self)			->				Optional[int]:
            _A      :       str				    = self.get_edges()
            for edge in edges:
                   _A      :       Dict				    = edge
                   edges.remove((tail, head, weight))
            for i in range(len(__lowerCamelCase)):
                   _A      :       Dict				    = list(edges[i])

            edges.sort(key=lambda __lowerCamelCase: e[2])
            for i in range(len(__lowerCamelCase) - 1):
                   if edges[i][2] >= edges[i + 1][2]:
                          _A      :       List[Any]				    = edges[i][2] + 1
            for edge in edges:
                   _A      :       Optional[Any]				    = edge
                   _A      :       str				    = weight
                   _A      :       Optional[int]				    = weight


     def __str__(						self)			->				str:
            _A      :       Union[str, Any]				    = """"""
            for tail in self.adjacency:
                   for head in self.adjacency[tail]:
                          _A      :       List[Any]				    = self.adjacency[head][tail]
                          string += F"{head} -> {tail} == {weight}\n"
            return string.rstrip("\n")


     def  _lowerCamelCase (						self)			->				Optional[int]:
            _A      :       Optional[int]				    = []
            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]:
            return self.adjacency.keys()


     @staticmethod
     def  _lowerCamelCase (						__lowerCamelCase=None ,						__lowerCamelCase=None)			->				str:
            _A      :       Optional[int]				    = Graph()
            if vertices is None:
                   _A      :       str				    = []
            if edges is None:
                   _A      :       Any				    = []
            for vertex in vertices:
                   g.add_vertex(__lowerCamelCase)
            for edge in edges:
                   g.add_edge(*__lowerCamelCase)
            return g







     class      lowerCAmelCase__       :




          '''simple docstring'''


          def __init__(						self)			->				Any:
                 _A      :       str				    = {}
                 _A      :       Dict				    = {}


          def __len__(						self)			->				str:
                 return len(self.parent)


          def  _lowerCamelCase (						self ,						__lowerCamelCase)			->				Tuple:






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

                 _A      :       Any				    = item
                 _A      :       int				    = 0
                 return item


          def  _lowerCamelCase (						self ,						__lowerCamelCase)			->				Dict:






                 if item not in self.parent:
                        return self.make_set(__lowerCamelCase)
                 if item != self.parent[item]:
                        _A      :       Union[str, Any]				    = self.find(self.parent[item])
                 return self.parent[item]


          def  _lowerCamelCase (						self ,						__lowerCamelCase ,						__lowerCamelCase)			->				int:
                 _A      :       Dict				    = self.find(__lowerCamelCase)
                 _A      :       Union[str, Any]				    = self.find(__lowerCamelCase)

                 if roota == roota:
                        return roota

                 if self.rank[roota] > self.rank[roota]:
                        _A      :       List[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      :       List[Any]				    = roota
                        return roota
                 return None




     @staticmethod
     def  _lowerCamelCase (						__lowerCamelCase)			->				List[Any]:
            _A      :       Dict				    = graph.num_vertices

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

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

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




"""simple docstring"""






import os
import sys
from contextlib import contextmanager


# Windows only
if os.name == "nt":
							import ctypes
							import msvcrt  # noqa





							class      lowerCamelCase__   (     ctypes.Structure				):







												"""simple docstring"""


												__a	       =							[("""size""", ctypes.c_int), ("""visible""", ctypes.c_byte)]
def      lowerCamelCase       (     )		->       Optional[int]:

							'''simple docstring'''



							if os.name == "nt":
														__UpperCAmelCase   :						Dict      							=					CursorInfo()
														__UpperCAmelCase   :						Any      							=					ctypes.windll.kernelaa.GetStdHandle(-1_1							)
														ctypes.windll.kernelaa.GetConsoleCursorInfo(_UpperCamelCase       ,			ctypes.byref(_UpperCamelCase							)							)
														__UpperCAmelCase   :						Tuple      							=					False
														ctypes.windll.kernelaa.SetConsoleCursorInfo(_UpperCamelCase       ,			ctypes.byref(_UpperCamelCase							)							)
							elif os.name == "posix":
														sys.stdout.write("""\033[?25l"""							)
														sys.stdout.flush()
def      lowerCamelCase       (     )		->       Optional[int]:

							'''simple docstring'''



							if os.name == "nt":
														__UpperCAmelCase   :						str      							=					CursorInfo()
														__UpperCAmelCase   :						int      							=					ctypes.windll.kernelaa.GetStdHandle(-1_1							)
														ctypes.windll.kernelaa.GetConsoleCursorInfo(_UpperCamelCase       ,			ctypes.byref(_UpperCamelCase							)							)
														__UpperCAmelCase   :						Union[str, Any]      							=					True
														ctypes.windll.kernelaa.SetConsoleCursorInfo(_UpperCamelCase       ,			ctypes.byref(_UpperCamelCase							)							)
							elif os.name == "posix":
														sys.stdout.write("""\033[?25h"""							)
														sys.stdout.flush()
@contextmanager
def      lowerCamelCase       (     )		->       str:

							'''simple docstring'''



							try:
														hide_cursor()
														yield
							finally:
														show_cursor()
