# UVa 10941

## Summary

Given two words ${\displaystyle x}$, ${\displaystyle y}$, and a dictionary with a number of words, it is allowed to append to ${\displaystyle x}$ and ${\displaystyle y}$ any words from the dictionary. Determine the minimum number of words that must be appended to make ${\displaystyle x}$ and ${\displaystyle y}$ equal.

## Explanation

The problem can be solved by BFS. The state in BFS is the unadjusted suffix of the longer of the two words.

## Trivia

The original problem by Wojciech Rytter was offered at Polish Olympiad in Informatics 1995/1996.

```2
abba
ab
4
aa
cc
a
ab
4
bb
ab
ba
aa
```

## Output

```5
-1
```

More test cases are available here.