





class 	UpperCamelCase__				:



     '''simple docstring'''

     def __init__(							self		:					List[str] )  ->	List[str]:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE	=		0
           SCREAMING_SNAKE_CASE	=		0
           SCREAMING_SNAKE_CASE	=		{}






     def        SCREAMING_SNAKE_CASE__						(							self		:					Optional[int]		,lowerCamelCase__		:					Dict )  ->	Tuple:




           '''simple docstring'''


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






     def        SCREAMING_SNAKE_CASE__						(							self		:					Union[str, Any]		,lowerCamelCase__		:					int		,lowerCamelCase__		:					List[str]		,lowerCamelCase__		:					Optional[Any] )  ->	Any:




           '''simple docstring'''


           self.add_vertex(lowerCamelCase__ )
           self.add_vertex(lowerCamelCase__ )

           if head == tail:
                 return

           SCREAMING_SNAKE_CASE	=		weight
           SCREAMING_SNAKE_CASE	=		weight






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




           '''simple docstring'''


           SCREAMING_SNAKE_CASE	=		self.get_edges()
           for edge in edges:
                 SCREAMING_SNAKE_CASE,      SCREAMING_SNAKE_CASE,      SCREAMING_SNAKE_CASE	=		edge
                 edges.remove((tail, head, weight) )
           for i in range(len(lowerCamelCase__ ) ):
                 SCREAMING_SNAKE_CASE	=		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]:
                       SCREAMING_SNAKE_CASE	=		edges[i][2] + 1
           for edge in edges:
                 SCREAMING_SNAKE_CASE,      SCREAMING_SNAKE_CASE,      SCREAMING_SNAKE_CASE	=		edge
                 SCREAMING_SNAKE_CASE	=		weight
                 SCREAMING_SNAKE_CASE	=		weight






     def __str__(							self		:					Optional[Any] )  ->	str:




           '''simple docstring'''


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






     def        SCREAMING_SNAKE_CASE__						(							self		:					str )  ->	Optional[Any]:




           '''simple docstring'''


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






     def        SCREAMING_SNAKE_CASE__						(							self		:					Optional[int] )  ->	Tuple:




           '''simple docstring'''


           return self.adjacency.keys()






     @staticmethod
     def        SCREAMING_SNAKE_CASE__						(							lowerCamelCase__		:					Union[str, Any]=None		,lowerCamelCase__		:					Optional[Any]=None )  ->	List[Any]:




           '''simple docstring'''


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

     class 	UpperCamelCase__				:



          '''simple docstring'''

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




                '''simple docstring'''


                SCREAMING_SNAKE_CASE	=		{}
                SCREAMING_SNAKE_CASE	=		{}






          def __len__(							self		:					int )  ->	str:




                '''simple docstring'''


                return len(self.parent )






          def        SCREAMING_SNAKE_CASE__						(							self		:					int		,lowerCamelCase__		:					Union[str, Any] )  ->	Tuple:




                '''simple docstring'''


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

                SCREAMING_SNAKE_CASE	=		item
                SCREAMING_SNAKE_CASE	=		0
                return item






          def        SCREAMING_SNAKE_CASE__						(							self		:					Optional[int]		,lowerCamelCase__		:					str )  ->	Union[str, Any]:




                '''simple docstring'''


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






          def        SCREAMING_SNAKE_CASE__						(							self		:					List[Any]		,lowerCamelCase__		:					List[Any]		,lowerCamelCase__		:					List[Any] )  ->	Tuple:




                '''simple docstring'''


                SCREAMING_SNAKE_CASE	=		self.find(lowerCamelCase__ )
                SCREAMING_SNAKE_CASE	=		self.find(lowerCamelCase__ )

                if roota == roota:
                      return roota

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

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

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






     @staticmethod
     def        SCREAMING_SNAKE_CASE__						(							lowerCamelCase__		:					Union[str, Any] )  ->	List[str]:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE	=		graph.num_vertices

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

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

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









def      __lowercase     (   _SCREAMING_SNAKE_CASE				,		_SCREAMING_SNAKE_CASE			)				->     float:


      '''simple docstring'''


      _validate_point(_SCREAMING_SNAKE_CASE			)
      _validate_point(_SCREAMING_SNAKE_CASE			)
      if len(_SCREAMING_SNAKE_CASE			) != len(_SCREAMING_SNAKE_CASE			):
            raise ValueError("""Both points must be in the same n-dimensional space"""			)

      return float(sum(abs(a - b			) for a, b in zip(_SCREAMING_SNAKE_CASE				,		_SCREAMING_SNAKE_CASE			)			)			)



def      __lowercase     (   _SCREAMING_SNAKE_CASE			)				->     None:


      '''simple docstring'''


      if point:
            if isinstance(_SCREAMING_SNAKE_CASE				,		_SCREAMING_SNAKE_CASE			):
                  for item in point:
                        if not isinstance(_SCREAMING_SNAKE_CASE				,		(int, float)			):
                              SCREAMING_SNAKE_CASE	=		(
                                  """Expected a list of numbers as input, found """
                                  F"""{type(_SCREAMING_SNAKE_CASE			).__name__}"""
                              )
                              raise TypeError(_SCREAMING_SNAKE_CASE			)
            else:
                  SCREAMING_SNAKE_CASE	=		F"""Expected a list of numbers as input, found {type(_SCREAMING_SNAKE_CASE			).__name__}"""
                  raise TypeError(_SCREAMING_SNAKE_CASE			)
      else:
            raise ValueError("""Missing an input"""			)



def      __lowercase     (   _SCREAMING_SNAKE_CASE				,		_SCREAMING_SNAKE_CASE			)				->     float:


      '''simple docstring'''


      _validate_point(_SCREAMING_SNAKE_CASE			)
      _validate_point(_SCREAMING_SNAKE_CASE			)
      if len(_SCREAMING_SNAKE_CASE			) != len(_SCREAMING_SNAKE_CASE			):
            raise ValueError("""Both points must be in the same n-dimensional space"""			)

      return float(sum(abs(x - y			) for x, y in zip(_SCREAMING_SNAKE_CASE				,		_SCREAMING_SNAKE_CASE			)			)			)


if __name__ == "__main__":
      import doctest

      doctest.testmod()


