





from __future__ import annotations

from collections import deque
from enum import Enum
from math import atana, degrees
from sys import maxsize



class 				_lowerCAmelCase			(	UpperCAmelCase_							):


  '''simple docstring'''
  a_							:				str					    =1
  a_							:				List[Any]					    =2
  a_							:				Optional[int]					    =3







  def __repr__(					self					:    Tuple							):


    '''simple docstring'''





    return f"""{self.__class__.__name__}.{self.name}"""




def 			lowerCamelCase_		(					lowerCAmelCase:		tuple[int, int]			,							lowerCAmelCase:		int			,							lowerCAmelCase:		int )->						float:
  _snake_case							,    _snake_case      : Optional[Any]														=		point
  return degrees(atana(y - miny			,							x - minx ) )


def 			lowerCamelCase_		(					lowerCAmelCase:		tuple[int, int]			,							lowerCAmelCase:		tuple[int, int]			,							lowerCAmelCase:		tuple[int, int] )->						Direction:
  _snake_case							,    _snake_case      : Any														=		starting
  _snake_case							,    _snake_case      : Tuple														=		via
  _snake_case							,    _snake_case      : Any														=		target
  _snake_case      : int														=		degrees(atana(ya - ya			,							xa - xa ) )
  via_angle %= 3_60
  _snake_case      : str														=		degrees(atana(ya - ya			,							xa - xa ) )
  target_angle %= 3_60
  # t-
  #  \ \
  #   \ v
  #    \|
  #     s
  # via_angle is always lower than target_angle, if direction is left.
  # If they are same, it means they are on a same line of convex hull.
  if target_angle > via_angle:
    return Direction.left
  elif target_angle == via_angle:
    return Direction.straight
  else:
    return Direction.right







def 			lowerCamelCase_		(					lowerCAmelCase:		list[tuple[int, int]] )->						list[tuple[int, int]]:

  if len(lowerCAmelCase ) <= 2:
    # There is no convex hull
    raise ValueError('graham_scan: argument must contain more than 3 points.' )
  if len(lowerCAmelCase ) == 3:
    return points
  # find the lowest and the most left point
  _snake_case      : Any														=		0
  _snake_case							,    _snake_case      : Tuple														=		maxsize, maxsize
  for i, point in enumerate(lowerCAmelCase ):
    _snake_case      : Any														=		point[0]
    _snake_case      : List[Any]														=		point[1]
    if y < miny:
      _snake_case      : str														=		y
      _snake_case      : int														=		x
      _snake_case      : Tuple														=		i
    if y == miny and x < minx:
      _snake_case      : Any														=		x
      _snake_case      : List[Any]														=		i

    # remove the lowest and the most left point from points for preparing for sort
  points.pop(lowerCAmelCase )

  _snake_case      : int														=		sorted(lowerCAmelCase			,							key=lambda lowerCAmelCase : angle_comparer(lowerCAmelCase			,							lowerCAmelCase			,							lowerCAmelCase ) )
  # This insert actually costs complexity,
  # and you should instead add (minx, miny) into stack later.
  # I'm using insert just for easy understanding.
  sorted_points.insert(0			,							(minx, miny) )

  _snake_case      : deque[tuple[int, int]]														=		deque()
  stack.append(sorted_points[0] )
  stack.append(sorted_points[1] )
  stack.append(sorted_points[2] )
  # In any ways, the first 3 points line are towards left.
  # Because we sort them the angle from minx, miny.
  _snake_case      : Optional[int]														=		Direction.left

  for i in range(3			,							len(lowerCAmelCase ) ):
    while True:
      _snake_case      : Tuple														=		stack[-2]
      _snake_case      : Tuple														=		stack[-1]
      _snake_case      : str														=		sorted_points[i]
      _snake_case      : Optional[Any]														=		check_direction(lowerCAmelCase			,							lowerCAmelCase			,							lowerCAmelCase )

      if next_direction == Direction.left:
        _snake_case      : int														=		Direction.left
        break
      if next_direction == Direction.straight:
        if current_direction == Direction.left:
          # We keep current_direction as left.
          # Because if the straight line keeps as straight,
          # we want to know if this straight line is towards left.
          break
        elif current_direction == Direction.right:
          # If the straight line is towards right,
          # every previous points on those straigh line is not convex hull.
          stack.pop()
      if next_direction == Direction.right:
        stack.pop()
    stack.append(sorted_points[i] )
  return list(lowerCAmelCase )











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

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

  _snake_case      : Dict														=		list(range(len(lowerCAmelCase ) + 1 ) )

  for i, ca in enumerate(lowerCAmelCase ):
    _snake_case      : Optional[int]														=		[i + 1]

    for j, ca in enumerate(lowerCAmelCase ):
      # Calculate insertions, deletions and substitutions
      _snake_case      : Optional[Any]														=		previous_row[j + 1] + 1
      _snake_case      : Optional[int]														=		current_row[j] + 1
      _snake_case      : Union[str, 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
    _snake_case      : str														=		current_row

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


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

      lowerCAmelCase_        =			levenshtein_distance(first_word, second_word)
      print(F"""Levenshtein distance between {first_word} and {second_word} is {result}""")




