농부 존은 소들과 다음과 같은 단어 게임을 하고 있다.

게임은

• 먼저 그가 선택할 수 있는 단어를 선택한다. 예로 'cat'
• 다음 소들이 단어를 선택한다. 예로 'dog'

프로그램에서 사전파일(dict.txt)를 읽어서 처리해야 한다.

사전에는 최대 25,000 단어를 포함있고 각 단어의 크기는 최대 1..20 까지이다. 그리고 사전에는 소문자 'a' .. 'z' 만이 포함되어 있다.

예를 들어 , 존은 다음과 같이 3 동작으로 원하는 결과를 만들 수 있다.

      'cat' -> 'cot' -> 'cog' -> 'dog'

첫 수와 끝수가 주어질 때 최소 동작수를 구하는 것이 문제이다.

입력

• Line 1: 첫 단어
• Line 2: 끝 단어

출력

입출력 예

입력

cat
dog

출력

3

입력 설명

출처:usaco 2010 JAN bronze