단어 변형

농부 존이 소들과 단어 게임을 합니다. 게임은 다음과 같이 진행됩니다.

• 농부 존이 먼저 단어 하나를 고릅니다. 예를 들어 cat.
• 소들도 자신들의 단어를 고릅니다. 예를 들어 dog.

이제 농부 존은 자신의 단어를 소들의 단어로 바꿔야 합니다. 이때 한 번에 한 글자씩만 바꾸어 새로운 유효한 단어를 만드는 과정을 여러 번 반복합니다. 여기서 유효한 단어란 입력으로 주어지는 사전에 들어 있는 단어를 뜻합니다.

예를 들어 농부 존은 다음과 같이 단어를 이어서 만들 수 있습니다.

cat -> cot -> cog -> dog

이렇게 하면 단 세 번의 변경만으로 cat을 dog로 변형할 수 있습니다. 소들은 절대 불가능한 문제를 내지 않으므로, 변형은 항상 가능합니다. 농부 존은 가능한 한 적은 횟수로 자신의 단어를 소들의 단어로 바꿔야 합니다.

시작 단어와 끝 단어가 주어질 때, 시작 단어를 끝 단어로 변형하는 데 필요한 최소 글자 변경 횟수를 구해서 출력하세요. 한 번의 변경은 정확히 한 글자만 바꾸며, 바뀐 뒤의 단어도 반드시 사전에 들어 있어야 합니다.

• 첫째 줄: 사전에 들어 있는 단어의 개수 $N$
• 다음 $N$개의 줄: 사전에 들어 있는 단어가 한 줄에 하나씩 주어집니다
• 그다음 줄: 시작 단어
• 그다음 줄: 끝 단어

모든 단어는 소문자 알파벳으로만 이루어져 있습니다. 시작 단어와 끝 단어는 반드시 사전에 포함되어 있으며, 시작 단어에서 끝 단어로 가는 변형은 항상 존재합니다.

• 첫째 줄: 시작 단어를 끝 단어로 변형하는 데 필요한 최소 글자 변경 횟수를 나타내는 정수 하나