def lev(s1, s2):
    if len(s1) < len(s2):
        return lev(s2, s1)

    # len(s1) >= len(s2)
    if len(s2) == 0:
        return len(s1)
 
    previous_row = range(len(s2) + 1)
    for i, c1 in enumerate(s1):
        current_row = [i + 1]
        for j, c2 in enumerate(s2):
            insertions = previous_row[j + 1] + 1 # j+1 instead of j since previous_row and current_row are one character longer
            deletions = current_row[j] + 1       # than s2
            substitutions = previous_row[j] + (c1 != c2)
            current_row.append(min(insertions, deletions, substitutions))
        previous_row = current_row
 
    return previous_row[-1]

s1=raw_input()
s2=raw_input()

def printAllLevSteps(s1, s2):
    if len(s1) < len(s2):
        s1, s2 = s2, s1
    chars = set(s2)
    while s1 != s2:
        oldS1 = s1
        for i in range(len(s1)*2):
            temp = list(s1)
            if i % 2 == 0:
                del(temp[i/2]) #Remove char #i from temp
            temp = "".join(temp)
            if lev(temp, s2) < lev(s1, s2):
                s1 = temp
                break
            if s1 != oldS1: # For some reason before the loop wouldn't stop
                break       # so I added this and now it's fine. Don't ask.
            for char in chars:
                temp = list(s1)      # Make it into a list
                temp[i/2] = char       # Make char #i to variable char
                temp = "".join(temp) # Convert it to a string
                if lev(temp, s2) < lev(s1, s2):
                    s1 = temp
                    break
        print s1
    
print "Distance:",lev(s1, s2)
print "Steps:"
printAllLevSteps(s1, s2)