You are given two strings BEGIN and END and an array of strings DICT. Your task is to find the length of the shortest transformation sequence from BEGIN to END such that in every transformation you can change exactly one alphabet and the word formed after each transformation must exist in DICT.
1. If there is no possible path to change BEGIN to END then just return -1.
2. All the words have the same length and contain only lowercase english alphabets.
3. The beginning word i.e. BEGIN will always be different from the end word i.e. END (BEGIN != END).
Input format :
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains a string BEGIN.
The second line of each test case contains a string END.
The third line of each test case contains a single integer N denoting the length of the DICT i.e. the array of strings.
The fourth line of each test case contains N space-separated strings denoting the strings present in the DICT array.
Output format :
For each test case, print a single integer representing the length of the shortest transformation sequence from BEGIN to END.
The output of each test case will be printed in a separate line.
You don’t have to print anything; it has already been taken care of. Just implement the given function.
1 <= T <= 5
1 <= N<= 10^2
1 <= |S| <= 10^2
Where ‘T’ is the total number of test cases, ‘N’ denotes the length of the DICT array and |S| represents the length of each string.
Sample Input 1 :
poa pro bro say pra
Sample Output 1 :
Explanation of The Sample Input 1:
For the first test case:
The given BEGIN word is ‘goa’ and the target word is ‘pro’ and the array we have is [poa, pro, bro, say, pra ].o firstly we can move from ‘goa’ to ‘poa’ after that we can move from ‘poa’ to ‘pra’ and finally we can move from ‘pra’ to ‘pro’.
Like the series "goa" -> "poa" -> "pra" -> "pro" therefore the length of the shortest transformation sequence from ‘goa’ to ‘pro’ will be 4.
Sample Input 2 :
pbvd tvgj perd peed prwq feeq prrd prrq
abg afg efg acd bgk
dfg acx teg qwq xcv ujy
Sample Output 2 :