4

Difficulty: HARD
Contributed By
Naresh
Avg. time to solve
10 min
Success Rate
90%

Problem Statement

#### Note:

``````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.
``````
##### Note:
``````You don’t have to print anything; it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````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 :
``````1
goa
pro
5
poa pro bro say pra
``````
##### Sample Output 1 :
``````4
``````
##### 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 :
``````3
feed
prrq
8
pbvd tvgj perd peed prwq feeq prrd prrq
abc
efg
5
abg afg efg acd bgk
bcm
lpq
6
dfg acx teg qwq xcv ujy
``````
##### Sample Output 2 :
``````5
4
-1
``````
Console