Word Ladder

Jon likes to play games of Word Ladder. In a game of word ladder a starting word $S$ and an ending word $E$ both of length $N$ are chosen. Jon starts with the starting word and in one step can change exactly one letter of his current word to form another word. The aim of the game is to transform the starting word into the ending word in the least amount of steps.

At every step in this process the words need to be valid words. For every game there is a list of $M$ valid words $W_0, W_1, \cdots, W_{M-1}$.

For example, if the starting word is HEAD and the ending word is TAIL, Jon could win the game in five steps as follows: HEAD -> HEAL -> TEAL -> TELL -> TALL -> TAIL

Jon is about to play a game of competitive word ladder against Iván and Jon wants to win. To win he must get from the starting word to the ending word in the least number of steps. To assure his victory, Jon has bribed the organisers and already knows the starting word, end word and the valid word list. On top of that, he has enough money to bribe the organisers into adding up to $K$ extra words into the valid word list.

You have been tasked with figuring out what is the least amount of steps Jon can win the game in if he selects the up to $K$ extra valid words optimally. Note that it may not be possible to win the game with $K$ extra words.

Input

• The first line contains three space-separated integers $N$, $M$ and $K$ - the length of each valid word, the number of valid words and the number of valid words you can add.
• The second line contains $S$ - The starting word
• The third line contains $E$ - The target word
• The next $M$ lines contains the valid words. Every line will have a single word of length $N$ composed only of uppercase English characters

Output

If it is possible to win the game, output a single integer - the least amount of steps Jon can win the game in if he selects the extra words optimally.

If it is not possible to win the game, print IMPOSSIBLE (without the quotes).

Constraints

• $0 \le K \le 100$
• $1 \le N \le 100$
• $2 \le M \le 100$
• $S \ne E$
• All words ($S$, $E$ and $W_i$) are composed only of uppercase english letters.
• $S$ and $E$ are included in the list of valid words.
• All valid words are distinct

Subtasks

• Subtask 1 (+15%): $M=2$. That is, there are only two valid words and they must be $S$ and $E$.
• Subtask 2 (+20%): $K=0$
• Subtask 3 (+20%): $K \le 1$
• Subtask 4 (+20%): $N \le 6$ and $K \le 10$. Additionally - $S$, $E$ and all valid words are composed only of the letters A, B, C, D or E.
• Subtask 5 (+25%): No further constraints

Sample Explanations

Sample One

In this sample, we cannot add any extra words. The solution is the same as the example described in the problem statement.

Sample Two

In this sample, we can add at most two extra words. However, no set of words make the game possible.

Sample Three

This sample is the same as sample one except that we can add up two extra words to the valid words list. If we add the words HAAL and HAIL (note that these do not need to be actual English words). Then Jon can win in four moves with HEAD -> HEAL -> HAAL -> HAIL -> TAIL. Other solutions are possible.

Note

If you are using Python and your solution is exceeding the time limit, try selecting Python 3.6 (PyPy 7.3) when submitting as this will generally make your code run faster.