Edit Distance

Given two strings \(S\) and \(T\), your task is to calculate the minimum number of operations needed to convert string \(S\) into string \(T\). The allowed operations are:

• Insertion of a single character
• Deletion of a single character
• Substitution (replacement) of a single character

This problem is a classic example of computing the Edit Distance between two strings. The solution is typically implemented using a dynamic programming approach. The recurrence relation can be written in LaTeX as:

\[ \text{dp}[i][j] = \begin{cases} j, & \text{if } i = 0, \\ i, & \text{if } j = 0, \\ \text{dp}[i-1][j-1], & \text{if } S_i = T_j, \\ 1 + \min\{\text{dp}[i-1][j],\, \text{dp}[i][j-1],\, \text{dp}[i-1][j-1]\}, & \text{otherwise.} \end{cases} \]

where \(S_i\) and \(T_j\) denote the \(i\)-th and \(j\)-th characters of strings \(S\) and \(T\) respectively.

inputFormat

The input is given via standard input (stdin) and consists of two lines:

1. The first line contains the string \(S\).
2. The second line contains the string \(T\).

Both strings may include only standard ASCII characters and have lengths not exceeding 1000.

outputFormat

Output a single integer to standard output (stdout) which represents the minimum number of operations required to convert \(S\) into \(T\).

## sample

abc
yabd

2