



'''simple docstring'''





class  lowerCamelCase_   :
  """simple docstring"""




  def __init__(			self				:     Tuple      ,     _a				:     Any       ) -> int:
    __lowerCamelCase	:	Tuple   	=			val
    # Number of nodes in left subtree
    __lowerCamelCase	:	Dict   	=			0
    __lowerCamelCase	:	List[Any]   	=			None
    __lowerCamelCase	:	List[Any]   	=			None
    __lowerCamelCase	:	Any   	=			None




  def 						_lowercase					(			self				:     List[str]      ,     _a				:     Tuple       ) -> Tuple:
    assert self.left_tree_size == other.left_tree_size, "Unequal Sizes of Blocks"

    if self.val < other.val:
      __lowerCamelCase	:	Dict   	=			self.right
      __lowerCamelCase	:	Any   	=			None
      if self.right:
        __lowerCamelCase	:	Dict   	=			other
      __lowerCamelCase	:	List[str]   	=			other
      __lowerCamelCase	:	Optional[int]   	=			self.left_tree_size * 2 + 1
      return self
    else:
      __lowerCamelCase	:	Union[str, Any]   	=			other.right
      __lowerCamelCase	:	Any   	=			None
      if other.right:
        __lowerCamelCase	:	int   	=			self
      __lowerCamelCase	:	Optional[int]   	=			self
      __lowerCamelCase	:	Dict   	=			other.left_tree_size * 2 + 1
      return other






class  lowerCamelCase_   :
  """simple docstring"""




  def __init__(			self				:     Optional[Any]      ,     _a				:     List[str]=None      ,     _a				:     Optional[Any]=None      ,     _a				:     Optional[Any]=0       ) -> str:
    __lowerCamelCase	:	List[Any]   	=			heap_size
    __lowerCamelCase	:	Optional[Any]   	=			bottom_root
    __lowerCamelCase	:	Optional[int]   	=			min_node




  def 						_lowercase					(			self				:     Optional[int]      ,     _a				:     str       ) -> List[str]:


    if other.size == 0:
      return None
    if self.size == 0:
      __lowerCamelCase	:	Any   	=			other.size
      __lowerCamelCase	:	List[Any]   	=			other.bottom_root
      __lowerCamelCase	:	int   	=			other.min_node
      return None
    # Update size
    __lowerCamelCase	:	Dict   	=			self.size + other.size

    # Update min.node
    if self.min_node.val > other.min_node.val:
      __lowerCamelCase	:	List[str]   	=			other.min_node
    # Merge

    # Order roots by left_subtree_size
    __lowerCamelCase	:	Tuple   	=			[]
    __lowerCamelCase	,__lowerCamelCase	:	Optional[Any]   	=			self.bottom_root, other.bottom_root
    while i or j:
      if i and ((not j) or i.left_tree_size < j.left_tree_size):
        combined_roots_list.append((i, True)       )
        __lowerCamelCase	:	str   	=			i.parent
      else:
        combined_roots_list.append((j, False)       )
        __lowerCamelCase	:	str   	=			j.parent
        # Insert links between them
    for i in range(len(_UpperCAmelCase       ) - 1       ):
      if combined_roots_list[i][1] != combined_roots_list[i + 1][1]:
        __lowerCamelCase	:	Optional[Any]   	=			combined_roots_list[i + 1][0]
        __lowerCamelCase	:	int   	=			combined_roots_list[i][0]
        # Consecutively merge roots with same left_tree_size
    __lowerCamelCase	:	Any   	=			combined_roots_list[0][0]
    while i.parent:
      if (
          (i.left_tree_size == i.parent.left_tree_size) and (not i.parent.parent)
      ) or (
          i.left_tree_size == i.parent.left_tree_size
          and i.left_tree_size != i.parent.parent.left_tree_size
      ):
        # Neighbouring Nodes
        __lowerCamelCase	:	int   	=			i.left
        __lowerCamelCase	:	Optional[int]   	=			i.parent.parent

        # Merging trees
        __lowerCamelCase	:	int   	=			i.merge_trees(i.parent       )

        # Updating links
        __lowerCamelCase	:	List[str]   	=			previous_node
        __lowerCamelCase	:	Any   	=			next_node
        if previous_node:
          __lowerCamelCase	:	str   	=			i
        if next_node:
          __lowerCamelCase	:	Any   	=			i
      else:
        __lowerCamelCase	:	Optional[int]   	=			i.parent
        # Updating self.bottom_root
    while i.left:
      __lowerCamelCase	:	int   	=			i.left
    __lowerCamelCase	:	str   	=			i

    # Update other
    __lowerCamelCase	:	int   	=			self.size
    __lowerCamelCase	:	List[str]   	=			self.bottom_root
    __lowerCamelCase	:	Dict   	=			self.min_node

    # Return the merged heap
    return self




  def 						_lowercase					(			self				:     Union[str, Any]      ,     _a				:     List[Any]       ) -> Union[str, Any]:


    if self.size == 0:
      __lowerCamelCase	:	Optional[Any]   	=			Node(_UpperCAmelCase       )
      __lowerCamelCase	:	Any   	=			1
      __lowerCamelCase	:	str   	=			self.bottom_root
    else:
      # Create new node
      __lowerCamelCase	:	List[str]   	=			Node(_UpperCAmelCase       )

      # Update size
      self.size += 1

      # update min_node
      if val < self.min_node.val:
        __lowerCamelCase	:	Any   	=			new_node
      # Put new_node as a bottom_root in heap
      __lowerCamelCase	:	List[Any]   	=			new_node
      __lowerCamelCase	:	Any   	=			self.bottom_root
      __lowerCamelCase	:	List[str]   	=			new_node

      # Consecutively merge roots with same left_tree_size
      while (
          self.bottom_root.parent
          and self.bottom_root.left_tree_size
          == self.bottom_root.parent.left_tree_size
      ):
        # Next node
        __lowerCamelCase	:	List[Any]   	=			self.bottom_root.parent.parent

        # Merge
        __lowerCamelCase	:	Any   	=			self.bottom_root.merge_trees(self.bottom_root.parent       )

        # Update Links
        __lowerCamelCase	:	Union[str, Any]   	=			next_node
        __lowerCamelCase	:	Tuple   	=			None
        if next_node:
          __lowerCamelCase	:	str   	=			self.bottom_root




  def 						_lowercase					(			self				:     Optional[int]       ) -> Tuple:
    return self.min_node.val




  def 						_lowercase					(			self				:     Optional[int]       ) -> List[Any]:
    return self.size == 0




  def 						_lowercase					(			self				:     Optional[int]       ) -> Optional[Any]:
    __lowerCamelCase	:	Dict   	=			self.min_node.val

    # Last element in heap corner case
    if self.size == 1:
      # Update size
      __lowerCamelCase	:	int   	=			0

      # Update bottom root
      __lowerCamelCase	:	List[Any]   	=			None

      # Update min_node
      __lowerCamelCase	:	List[Any]   	=			None

      return min_value
    # No right subtree corner case
    # The structure of the tree implies that this should be the bottom root
    # and there is at least one other root
    if self.min_node.right is None:
      # Update size
      self.size -= 1

      # Update bottom root
      __lowerCamelCase	:	Dict   	=			self.bottom_root.parent
      __lowerCamelCase	:	Any   	=			None

      # Update min_node
      __lowerCamelCase	:	Union[str, Any]   	=			self.bottom_root
      __lowerCamelCase	:	Dict   	=			self.bottom_root.parent
      while i:
        if i.val < self.min_node.val:
          __lowerCamelCase	:	Union[str, Any]   	=			i
        __lowerCamelCase	:	Optional[int]   	=			i.parent
      return min_value
    # General case
    # Find the BinomialHeap of the right subtree of min_node
    __lowerCamelCase	:	str   	=			self.min_node.right
    __lowerCamelCase	:	Any   	=			None
    __lowerCamelCase	:	Optional[Any]   	=			bottom_of_new
    __lowerCamelCase	:	str   	=			1

    # Size, min_node and bottom_root
    while bottom_of_new.left:
      __lowerCamelCase	:	Dict   	=			size_of_new * 2 + 1
      __lowerCamelCase	:	Dict   	=			bottom_of_new.left
      if bottom_of_new.val < min_of_new.val:
        __lowerCamelCase	:	Optional[Any]   	=			bottom_of_new
        # Corner case of single root on top left path
    if (not self.min_node.left) and (not self.min_node.parent):
      __lowerCamelCase	:	int   	=			size_of_new
      __lowerCamelCase	:	int   	=			bottom_of_new
      __lowerCamelCase	:	Tuple   	=			min_of_new
      # print("Single root, multiple nodes case")
      return min_value
    # Remaining cases
    # Construct heap of right subtree
    __lowerCamelCase	:	str   	=			BinomialHeap(
        bottom_root=_UpperCAmelCase      ,     min_node=_UpperCAmelCase      ,     heap_size=_UpperCAmelCase       )

    # Update size
    __lowerCamelCase	:	str   	=			self.size - 1 - size_of_new

    # Neighbour nodes
    __lowerCamelCase	:	List[str]   	=			self.min_node.left
    __lowerCamelCase	:	Optional[Any]   	=			self.min_node.parent

    # Initialize new bottom_root and min_node
    __lowerCamelCase	:	Tuple   	=			previous_node or next_node
    __lowerCamelCase	:	Any   	=			next_node

    # Update links of previous_node and search below for new min_node and
    # bottom_root
    if previous_node:
      __lowerCamelCase	:	Optional[int]   	=			next_node

      # Update bottom_root and search for min_node below
      __lowerCamelCase	:	List[Any]   	=			previous_node
      __lowerCamelCase	:	Tuple   	=			previous_node
      while self.bottom_root.left:
        __lowerCamelCase	:	Any   	=			self.bottom_root.left
        if self.bottom_root.val < self.min_node.val:
          __lowerCamelCase	:	Any   	=			self.bottom_root
    if next_node:
      __lowerCamelCase	:	Optional[Any]   	=			previous_node

      # Search for new min_node above min_node
      __lowerCamelCase	:	Any   	=			next_node
      while i:
        if i.val < self.min_node.val:
          __lowerCamelCase	:	Union[str, Any]   	=			i
        __lowerCamelCase	:	Tuple   	=			i.parent
        # Merge heaps
    self.merge_heaps(_UpperCAmelCase       )

    return min_value




  def 						_lowercase					(			self				:     Optional[Any]       ) -> Tuple:
    __lowerCamelCase	:	List[str]   	=			self.bottom_root
    while top_root.parent:
      __lowerCamelCase	:	List[Any]   	=			top_root.parent
    # preorder
    __lowerCamelCase	:	List[str]   	=			[]
    self.__traversal(_UpperCAmelCase      ,     _UpperCAmelCase       )
    return heap_pre_order




  def 						_lowercase					(			self				:     Tuple      ,     _a				:     List[Any]      ,     _a				:     Any      ,     _a				:     Tuple=0       ) -> Any:


    if curr_node:
      preorder.append((curr_node.val, level)       )
      self.__traversal(curr_node.left      ,     _UpperCAmelCase      ,     level + 1       )
      self.__traversal(curr_node.right      ,     _UpperCAmelCase      ,     level + 1       )
    else:
      preorder.append(('#', level)       )




  def __str__(			self				:     Optional[int]       ) -> Dict:


    if self.is_empty():
      return ""
    __lowerCamelCase	:	Optional[int]   	=			self.pre_order()

    return "\n".join(('-' * level + str(_UpperCAmelCase       )) for value, level in preorder_heap       )


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

   doctest.testmod()











'''simple docstring'''





def 	a_					(							_lowerCAmelCase	,_lowerCAmelCase	)				->				int:
  # The longer word should come first
  if len(_lowerCAmelCase	) < len(_lowerCAmelCase	):
    return levenshtein_distance(_lowerCAmelCase	,_lowerCAmelCase	)

  if len(_lowerCAmelCase	) == 0:
    return len(_lowerCAmelCase	)

  __lowerCamelCase	:	int   	=			list(range(len(_lowerCAmelCase	) + 1	)	)

  for i, ca in enumerate(_lowerCAmelCase	):
    __lowerCamelCase	:	Union[str, Any]   	=			[i + 1]

    for j, ca in enumerate(_lowerCAmelCase	):
      # Calculate insertions, deletions and substitutions
      __lowerCamelCase	:	Any   	=			previous_row[j + 1] + 1
      __lowerCamelCase	:	int   	=			current_row[j] + 1
      __lowerCamelCase	:	Any   	=			previous_row[j] + (ca != ca)

      # Get the minimum to append to the current row
      current_row.append(min(_lowerCAmelCase	,_lowerCAmelCase	,_lowerCAmelCase	)	)

    # Store the previous row
    __lowerCamelCase	:	Optional[int]   	=			current_row

  # Returns the last element (distance)
  return previous_row[-1]


if __name__ == "__main__":
   _UpperCamelCase							    =						input('Enter the first word:\n').strip()
   _UpperCamelCase							    =						input('Enter the second word:\n').strip()

   _UpperCamelCase							    =						levenshtein_distance(first_word, second_word)
   print(f'''Levenshtein distance between {first_word} and {second_word} is {result}''')






