Cousin Strings

Time limit1sMemory limit128 MB

Summary

Find the smallest n such that x is an n-th cousin of y, where each cousin step requires a common string reachable by deleting at most half of each string, or report that no n exists.

Level: Medium7 of 10
Topics: Graph, BFS, String, Dynamic programming
Solved: No attempts yet

Problem

Two strings $a$ and $b$ are called first cousins if they can be made equal by deleting at most half of the characters from each string. For example, abcdef and axcyd are first cousins: deleting $3$ of the $6$ characters (b, e, f) from the first string and $2$ of the $5$ characters (x, y) from the second string leaves acd in both cases.

Two strings $c$ and $d$ are called $(n{+}1)$ -th cousins if there exists a string $e$ that is a first cousin of $c$ and an $n$ -th cousin of $d$ .

Given two strings $x$ and $y$ , find the smallest $n \ge 1$ such that $x$ is an $n$ -th cousin of $y$ .

Input

The input contains several test cases. Each test case consists of two lines: the string $x$ on the first line and the string $y$ on the second line. Each of $x$ and $y$ contains between $1$ and $100$ lowercase letters. The input ends with a test case whose two lines each contain a single 0; this terminating case must not be processed.

Output

For each test case, print a single line containing the smallest $n$ for which $x$ is an $n$ -th cousin of $y$ , or not related if no such $n$ exists.

Examples3

Example 1
Input
```
a
b
abb
baa
abcdef
axcyd
0
0
```
Expected output
```
2
2
1
```
Example 2
Input
```
abc
abc
z
z
0
0
```
Expected output
```
1
1
```
Example 3
Input
```
x
y
0
0
```
Expected output
```
2
```