단어 사다리

단어 사다리는 글자를 한 번에 하나씩 바꾸어 한 단어를 다른 단어로 만드는 퍼즐이다. 조건이 하나 붙는다. 바꾸는 도중에 나오는 단어가 모두 사전에 있어야 한다. CAT을 GAS로 바꾸는 방법 하나는 다음과 같다.

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

바꾸는 횟수는 적을수록 좋다. 퍼즐이 어려워지면 단어 하나만 사전에 더 있었으면 좋겠다는 생각이 들기 마련이다.

사전이 주어진다. 사전의 첫 번째 단어가 시작 단어이고, 두 번째 단어가 끝 단어이다. 사전에 없는 단어를 하나만 골라 사전에 넣어서 시작 단어에서 끝 단어까지 가는 단계 수를 가장 작게 만들어라. 한 단계에서는 글자 하나만 바꾸고, 거쳐 가는 단어는 모두 사전에 있어야 한다. 추가하는 단어는 사전에 있는 단어와 길이가 같고 알파벳 대문자로만 이루어진다.

입력은 테스트 케이스 하나로 이루어진다. 첫째 줄에 사전에 들어 있는 단어의 개수 $n$이 주어진다 ($2 \le n \le 1000$). 다음 $n$개 줄에 단어가 한 줄에 하나씩 주어진다. 모든 단어는 길이가 1 이상 8 이하이고 알파벳 대문자로만 이루어져 있다. 한 입력에 나오는 단어의 길이는 모두 같고, 같은 단어가 두 번 나오지 않는다. 첫 번째 단어가 시작 단어, 두 번째 단어가 끝 단어이다.

정확히 두 줄을 출력한다. 첫째 줄에는 사전에 추가할 단어를, 둘째 줄에는 그 단어를 추가했을 때 시작 단어에서 끝 단어까지 가는 최소 단계 수를 출력한다. 공백은 출력하지 않는다.

단계 수를 가장 작게 만드는 단어가 여러 개면 사전순으로 가장 앞선 단어를 출력한다.

단어를 추가하기 전에는 끝 단어에 갈 수 없었는데 추가한 뒤에 갈 수 있게 되면, 이것도 단계 수가 줄어든 경우로 본다.

어떤 단어를 추가해도 단계 수가 줄지 않으면 첫째 줄에 0을 출력하고, 둘째 줄에는 사전을 그대로 두었을 때의 최소 단계 수를 출력한다.

어떤 단어를 추가해도 시작 단어에서 끝 단어까지 갈 수 없으면 첫째 줄에 0을, 둘째 줄에 -1을 출력한다.