





class     _UpperCAmelCase   :

  """simple docstring"""


  def __init__(    self			:		Dict					)							->						str:
     __lowerCAmelCase							     =     0
     __lowerCAmelCase							     =     0
     __lowerCAmelCase							     =     {}






  def     lowercase		(    self			:		List[Any] ,  lowerCAmelCase_			:		Dict					)							->						str:
     if vertex not in self.adjacency:
        __lowerCAmelCase							     =     {}
        self.num_vertices += 1






  def     lowercase		(    self			:		Union[str, Any] ,  lowerCAmelCase_			:		List[str] ,  lowerCAmelCase_			:		int ,  lowerCAmelCase_			:		Dict					)							->						int:
     self.add_vertex(SCREAMING_SNAKE_CASE_					)
     self.add_vertex(SCREAMING_SNAKE_CASE_					)

     if head == tail:
        return

     __lowerCAmelCase							     =     weight
     __lowerCAmelCase							     =     weight






  def     lowercase		(    self			:		str					)							->						Tuple:
     __lowerCAmelCase							     =     self.get_edges()
     for edge in edges:
        __lowerCAmelCase							     =     edge
        edges.remove((tail, head, weight)					)
     for i in range(len(SCREAMING_SNAKE_CASE_					)					):
        __lowerCAmelCase							     =     list(edges[i]					)

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






  def __str__(    self			:		Optional[int]					)							->						str:
     __lowerCAmelCase							     =     """"""
     for tail in self.adjacency:
        for head in self.adjacency[tail]:
           __lowerCAmelCase							     =     self.adjacency[head][tail]
           string += f"""{head} -> {tail} == {weight}\n"""
     return string.rstrip('\n'					)






  def     lowercase		(    self			:		Tuple					)							->						Optional[int]:
     __lowerCAmelCase							     =     []
     for tail in self.adjacency:
        for head in self.adjacency[tail]:
           output.append((tail, head, self.adjacency[head][tail])					)
     return output






  def     lowercase		(    self			:		str					)							->						Optional[int]:
     return self.adjacency.keys()






  @staticmethod
  def     lowercase		(    lowerCAmelCase_			:		int=None ,  lowerCAmelCase_			:		Dict=None					)							->						Optional[int]:
     __lowerCAmelCase							     =     Graph()
     if vertices is None:
        __lowerCAmelCase							     =     []
     if edges is None:
        __lowerCAmelCase							     =     []
     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			:		int					)							->						Any:
       __lowerCAmelCase							     =     {}
       __lowerCAmelCase							     =     {}






    def __len__(    self			:		Tuple					)							->						List[Any]:
       return len(self.parent					)






    def     lowercase		(    self			:		List[Any] ,  lowerCAmelCase_			:		Optional[int]					)							->						List[Any]:
       if item in self.parent:
          return self.find(SCREAMING_SNAKE_CASE_					)

       __lowerCAmelCase							     =     item
       __lowerCAmelCase							     =     0
       return item






    def     lowercase		(    self			:		Dict ,  lowerCAmelCase_			:		Tuple					)							->						Union[str, Any]:
       if item not in self.parent:
          return self.make_set(SCREAMING_SNAKE_CASE_					)
       if item != self.parent[item]:
          __lowerCAmelCase							     =     self.find(self.parent[item]					)
       return self.parent[item]






    def     lowercase		(    self			:		List[str] ,  lowerCAmelCase_			:		Optional[Any] ,  lowerCAmelCase_			:		Any					)							->						Optional[int]:
       __lowerCAmelCase							     =     self.find(SCREAMING_SNAKE_CASE_					)
       __lowerCAmelCase							     =     self.find(SCREAMING_SNAKE_CASE_					)

       if roota == roota:
          return roota

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

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

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






  @staticmethod
  def     lowercase		(    lowerCAmelCase_			:		int					)							->						Tuple:
     __lowerCAmelCase							     =     graph.num_vertices

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

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

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








import mpmath  # for roots of unity
import numpy as np



class     _UpperCAmelCase   :

  """simple docstring"""


  def __init__(    self			:		List[Any] ,  lowerCAmelCase_			:		Dict=None ,  lowerCAmelCase_			:		str=None					)							->						List[Any]:
     # Input as list
     __lowerCAmelCase							     =     list(poly_a or [0]					)[:]
     __lowerCAmelCase							     =     list(poly_b or [0]					)[:]

     # Remove leading zero coefficients
     while self.polyA[-1] == 0:
        self.polyA.pop()
     __lowerCAmelCase							     =     len(self.polyA					)

     while self.polyB[-1] == 0:
        self.polyB.pop()
     __lowerCAmelCase							     =     len(self.polyB					)

     # Add 0 to make lengths equal a power of 2
     __lowerCAmelCase							     =     int(
         2 ** np.ceil(np.loga(len(self.polyA					) + len(self.polyB					) - 1					)					)					)

     while len(self.polyA					) < self.c_max_length:
        self.polyA.append(0					)
     while len(self.polyB					) < self.c_max_length:
        self.polyB.append(0					)
     # A complex root used for the fourier transform
     __lowerCAmelCase							     =     complex(mpmath.root(x=1 ,  n=self.c_max_length ,  k=1					)					)

     # The product
     __lowerCAmelCase							     =     self.__multiply()






  def     lowercase		(    self			:		Optional[int] ,  lowerCAmelCase_			:		str					)							->						Optional[int]:
     __lowerCAmelCase							     =     [[x] for x in self.polyA] if which == 'A' else [[x] for x in self.polyB]
     # Corner case
     if len(lowerCAmelCase_					) <= 1:
        return dft[0]
     #
     __lowerCAmelCase							     =     self.c_max_length // 2
     while next_ncol > 0:
        __lowerCAmelCase							     =     [[] for i in range(lowerCAmelCase_					)]
        __lowerCAmelCase							     =     self.root**next_ncol

        # First half of next step
        __lowerCAmelCase							     =     1
        for j in range(self.c_max_length // (next_ncol * 2)					):
           for i in range(lowerCAmelCase_					):
              new_dft[i].append(dft[i][j] + current_root * dft[i + next_ncol][j]					)
           current_root *= root
        # Second half of next step
        __lowerCAmelCase							     =     1
        for j in range(self.c_max_length // (next_ncol * 2)					):
           for i in range(lowerCAmelCase_					):
              new_dft[i].append(dft[i][j] - current_root * dft[i + next_ncol][j]					)
           current_root *= root
        # Update
        __lowerCAmelCase							     =     new_dft
        __lowerCAmelCase							     =     next_ncol // 2
     return dft[0]






  def     lowercase		(    self			:		Optional[int]					)							->						Any:
     __lowerCAmelCase							     =     self.__dft('A'					)
     __lowerCAmelCase							     =     self.__dft('B'					)
     __lowerCAmelCase							     =     [[dft_a[i] * dft_b[i] for i in range(self.c_max_length					)]]
     del dft_a
     del dft_b

     # Corner Case
     if len(inverce_c[0]					) <= 1:
        return inverce_c[0]
     # Inverse DFT
     __lowerCAmelCase							     =     2
     while next_ncol <= self.c_max_length:
        __lowerCAmelCase							     =     [[] for i in range(lowerCAmelCase_					)]
        __lowerCAmelCase							     =     self.root ** (next_ncol // 2)
        __lowerCAmelCase							     =     1
        # First half of next step
        for j in range(self.c_max_length // next_ncol					):
           for i in range(next_ncol // 2					):
              # Even positions
              new_inverse_c[i].append(
                  (
                      inverce_c[i][j]
                      + inverce_c[i][j + self.c_max_length // next_ncol]
                  )
                  / 2					)
              # Odd positions
              new_inverse_c[i + next_ncol // 2].append(
                  (
                      inverce_c[i][j]
                      - inverce_c[i][j + self.c_max_length // next_ncol]
                  )
                  / (2 * current_root)					)
           current_root *= root
        # Update
        __lowerCAmelCase							     =     new_inverse_c
        next_ncol *= 2
     # Unpack
     __lowerCAmelCase							     =     [round(x[0].real ,  8					) + round(x[0].imag ,  8					) * 1J for x in inverce_c]

     # Remove leading 0's
     while inverce_c[-1] == 0:
        inverce_c.pop()
     return inverce_c






  def __str__(    self			:		Dict					)							->						int:
     __lowerCAmelCase							     =     'A = ' + ' + '.join(
         f"""{coef}*x^{i}""" for coef, i in enumerate(self.polyA[: self.len_A]					)					)
     __lowerCAmelCase							     =     'B = ' + ' + '.join(
         f"""{coef}*x^{i}""" for coef, i in enumerate(self.polyB[: self.len_B]					)					)
     __lowerCAmelCase							     =     'A*B = ' + ' + '.join(
         f"""{coef}*x^{i}""" for coef, i in enumerate(self.product					)					)

     return f"""{a}\n{b}\n{c}"""


# Unit tests
if __name__ == "__main__":
     import doctest

     doctest.testmod()

