Shortest Supersequences X40399

Find shortest supersequences of pairs of strings. A supersequence of a string s is a string t such that s is obtained from t by deleting zero or more characters. Given two strings s and t, of course the concatenation st is a supersequence of both; often, however, there are shorter ones. For instance, ’AGGXTXAYB’ is a shortest supersequence of ’AGGTAB’ and ’GXTXAYB’, while ’blueed’ and ’bleued’ are both shortest supersequences of ’bleed’ and ’blue’, and ’bacfkorward’ is one of the shortest supersequences of ’backward’ and ’forward’.

Input

Input is a sequence of cases. A case consists of two words s and t in the same line; both consist only of letters. Each line brings exactly one case.

Output

For each case, print the length of the shortest supersequences of both strings.

Observation

This is a classical example where one must apply Dynamic Programming. Note that there may be several different shortest supersequences; however, all must have the same length. The automatic correction will not want to see the shortest supersequences themselves: it only expects their length. However, along your programming and debugging task, it will be helpful to be able to write down for human eyes not only the length but also at least one of these shortest supersequences. Which one will you write? Are you able to construct your program so as to identify the alphabetically smallest shortest supersequence?