Word Ladder

A word ladder is a puzzle where you turn one word into another by changing a single letter at a time. There is one catch. Every word you form along the way has to be in the dictionary. Here is one way to turn CAT into GAS.

CAT -> CAR -> WAR -> WAS -> GAS

The fewer changes you use, the better. When a puzzle gets hard, it is tempting to wish that one particular word was in the dictionary.

You are given a dictionary. Its first word is the starting word and its second word is the ending word. Pick one word that is not in the dictionary, add it, and make the number of steps from the starting word to the ending word as small as possible. Each step changes one letter, and every word on the path must be in the dictionary. The word you add has the same length as the dictionary words and consists of capital letters only.

The input holds a single test case. The first line contains the number of words in the dictionary, $n$ ($2 \le n \le 1000$). Each of the next $n$ lines contains one word. Every word is 1 to 8 capital letters long. All words in one input have the same length, and no word appears twice. The first word is the starting word and the second word is the ending word.

Print exactly two lines. The first line holds the word you add to the dictionary, and the second line holds the minimum number of steps from the starting word to the ending word after the addition. Print no spaces.

If several words give the same smallest number of steps, print the one that comes first alphabetically.

If the ending word is unreachable before the addition and reachable after it, that counts as making the number of steps smaller.

If no word you add makes the number of steps smaller, print 0 on the first line, and print the minimum number of steps with the dictionary unchanged on the second line.

If the ending word stays unreachable no matter which word you add, print 0 on the first line and -1 on the second line.