문제1313--최적의 변환 순서 찾기

1313: 최적의 변환 순서 찾기

시간제한 : 1.000 sec  메모리제한 : 128 MB

문제 설명

시작 단어, 끝 단어, 단어 사전이 주어집니다. 시작 단어부터 한 번에 한 문자만 바꾸어 끝 단어를 만드는 최적의 순서를 찾아주세요. 그런데 중간 단어와 끝 단어는 반드시 단어 사전에 있어야 합니다. 중간 단어와 끝 단어가 단어 사전에 없으면 그 순서는 사용할 수 없습니다.

입력 설명

첫 줄에는 테스트케이스 T(1<=T<=100)가 주어집니다. 각 테스트케이스는 두 줄로 주어집니다. 첫 줄에는 시작 단어, 끝 단어, 단어 사전에 있는 단어 수 N(1<=N<=5,000)이 주어집니다. 둘째 줄에는 N개의 단어가 주어집니다. 특정 테스트케이스에 주어지는 단어의 길이는 모두 같으며, 영소문자로만 구성되어 있습니다. 단어 사전에는 중복된 단어는 포함되어 있지 않습니다. 단어의 길이는 최소 1, 최대 10입니다. 

출력 설명

각 테스트케이스마다 시작 단어를 끝 단어로 변환하기 위한 가장 최적의 순서를 찾아 그 순서에서 몇 번 문자를 바꾸었는지 출력해 주세요. 시작 단어를 끝 단어로 변환할 수 없다면 -1을 출력하여 주세요. 

입력 예시 Copy

3
hit cog 6
hot dot dog lot log cog
hit cog 5
hot dot dog lot log
a c 3
a b c

출력 예시 Copy

4
-1
1

도움

입력 예시에서 첫 번째 테스트케이스의 경우, hit => hot => dot => dog => cog가 가장 짧은 변환 순서이며, 총 4번 문자를 바꾸었으므로 4를 출력해야 한다.