Minimum Edit Distance Transformation

You are given two strings: a source string and a target string. Your task is to compute the minimum number of operations required to transform the source into the target. The allowed operations are:

• Insertion of a single character
• Deletion of a single character
• Substitution of one character for another

The edit distance between the two strings corresponds to the minimum number of such operations needed. Mathematically, if you denote by \(dp[i][j]\) the minimum edit distance between the first \(i\) characters of the source and the first \(j\) characters of the target, then the recurrence is given by:

\[ \text{dp}[i][j]=\begin{cases} j, & \text{if } i=0,\\ i, & \text{if } j=0,\\ \text{dp}[i-1][j-1], & \text{if } source[i-1]=target[j-1],\\ 1+\min\{\text{dp}[i-1][j],\;\text{dp}[i][j-1],\;\text{dp}[i-1][j-1]\}, & \text{if } source[i-1]\neq target[j-1]. \end{cases} \]

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

inputFormat

The input consists of two lines:

• The first line contains the source string.
• The second line contains the target string.

outputFormat

Output a single integer which is the minimum number of edit operations required to transform the source string into the target string.

## sample

kitten
sitting

3