def edit_dyn(s, t):

    m = len(s)
    n = len(t)

    D = [ [0] * (n+1) for i in range(0,m+1) ]
    A = [ [0] * (n+1) for i in range(0,m+1) ]

    for j in range(0, n+1):
        D[0][j] = j
        A[0][j] = 2
       
    for i in range(1, m+1):
        D[i][0] = i
        A[0][j] = 3
 
    for i in range (1, m+1):
        for j in range(1, n+1):
            D[i][j] = D[i-1][j-1]
            A[i][j] = 0
            if s[i-1] != t[j-1]:
                A[i][j] = 1
                if D[i][j-1] < D[i][j]:
                    D[i][j] = D[i][j-1]
                    A[i][j] = 2
                elif D[i-1][j] < D[i][j]:
                    D[i][j] = D[i-1][j]
                    A[i][j] = 3
                D[i][j] = D[i][j]+1
    def alignS(i,j):
        if (i == 0) and (j == 0):
            return ""
        elif (i == 0):
            return alignS(i,j-1)+"-"
        elif (j == 0):
            return s[0:i]
        elif (A[i][j]  == 0) or (A[i][j] == 1):
            return alignS(i-1,j-1)+s[i-1]
        elif (A[i][j] == 2):
            return alignS(i,j-1)+"-"
        else:
            return alignS(i-1,j)+s[i-1]
        
    def alignT(i,j):
        if (i == 0) and (j == 0):
            return ""
        elif (i == 0):
            return t[0:j]
        elif (j == 0):
            return alignT(i-1,j)+"-"
        elif (A[i][j]  == 0) or	(A[i][j] == 1):
            return alignT(i-1,j-1)+t[j-1]
        elif (A[i][j] == 2):
            return alignT(i,j-1)+t[j-1]
        else:
            return alignT(i-1,j)+"-"
    
    ss = alignS(m,n)
    tt = alignT(m,n)
    k = len(tt)
    print(ss)
    print(tt)


def memoize(f):
    memo = {}
    def check(s,t):
        if (s,t) not in memo:
            memo[(s,t)]=f(s,t)
            return memo[(s,t)]
    return check 

def edit_rec(s,t):
    if len(s) == 0:
        return len(t)
    elif len(t) ==0:
        return len(s)
    elif s[len(s)-1] == t[len(t)-1]:
        return edit_rec(s[:-1], t[:-1])
    else:
        return 1+ min(edit_rec(s,t[:-1]),edit_rec(s[:-1],t),edit_rec(s[:-1],t[:-1]))