output_description: Print the edit distance in a line.
input_description: s1
      s2
      
  
  Two words s1 and s2 are given in the first line and the second line
  respectively. The words will consist of lower case characters.
attempt: # ?????????http://ja.wikipedia.org/wiki/??¬??????????????\??????????????¢
  def levenshtein_distance(str1, str2):
      d = [[0] * (len(str2)) for _ in range(len(str1))]
  
      for i1 in range(len(str1)):
          d[i1][0] = i1
      for i2 in range(len(str2)):
          d[0][i2] = i2
  
      for i1 in range(1, len(str1)):
          for i2 in range(1, len(str2)):
              cost = 0 if str1[i1] == str2[i2] else 1
              d[i1][i2] = min(
                  d[i1 - 1][i2] + 1,  # ??????????????\
                  d[i1][i2 - 1] + 1,  # ???????????????
                  d[i1 - 1][i2 - 1] + cost,
              )  # ???????????????
      return d[-1][-1]
  
  
  from sys import stdin
  
  readline = stdin.readline
  
  
  s1, s2 = [readline().strip() for _ in range(2)]
  print(levenshtein_distance(s1, s2))
  
problem_description: Edit Distance (Levenshtein Distance)
  
    
  
  Find the edit distance between given two words s1 and s2.
  
  The disntace is the minimum number of single-character edits required to
  change one word into the other. The edits including the following operations:
  
    * **insertion** : Insert a character at a particular position.
    * **deletion** : Delete a character at a particular position. 
    * **substitution** : Change the character at a particular position to a different character
samples: [{"input": "acac\n    acm", "output": "2"}, {"input": "icpc\n    icpc", "output": "0"}]