Edit Distance Transformation

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

• Insertion of a single character
• Deletion of a single character
• Replacement of one character with another

This problem can be solved using the dynamic programming technique. The recurrence relation is formulated as follows:

\(dp[i][j] = \begin{cases} i & \text{if } j = 0 \\ j & \text{if } i = 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 input strings (each provided on a separate line), print the minimum number of operations needed to transform the source into the target.

inputFormat

The input consists of two lines:

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

Both strings may be empty.

outputFormat

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

## sample

kitten
sitting

3

</p>