Minimum Edit Distance

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

• Insertion of a character
• Deletion of a character
• Replacement of a character

The solution should be based on a dynamic programming approach. The recurrence relation can be formulated as follows:

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

Given the two strings as input (each in a separate line), output the minimum number of operations required to transform source into target.

inputFormat

The input consists of exactly two lines:

1. The first line contains the string source.
2. The second line contains the string target.

Both strings consist of lowercase English letters.

outputFormat

Output a single integer that represents the minimum edit distance between the two strings.

## sample

cat
cut

1