Minimum Operations to Transform Strings

You are given two strings s1 and s2. Your task is to compute the minimum number of operations required to transform s1 into s2 using the following allowed operations:

• Insertion
• Deletion
• Replacement

This is a classical edit distance problem. In mathematical terms, if we denote the edit distance by \(D(s_1, s_2)\), the recurrence relation is given by:

\[ D(i, j) = \begin{cases} j & \text{if } i = 0,\\ i & \text{if } j = 0,\\ D(i-1, j-1) & \text{if } s_1[i-1] = s_2[j-1],\\ 1 + \min\{ D(i-1, j),\, D(i, j-1),\, D(i-1, j-1) \} & \text{if } s_1[i-1] \neq s_2[j-1]. \end{cases} \]

Your solution should read the input from stdin and output the result to stdout.

inputFormat

The input consists of two lines:

1. The first line contains the string s1.
2. The second line contains the string s2.

Both strings can be empty.

outputFormat

Output a single integer representing the minimum number of operations required to transform s1 into s2.

## sample

kitten
sitting

3