Word Ladder Problem Statement

Given two strings, BEGIN and END, along with an array of strings DICT, determine the length of the shortest transformation sequence from BEGIN to END. Each transformation involves changing exactly one alphabet, and the resulting word after each transformation must be present in DICT.

Input:

Integer T representing number of test cases.
For each test case:
  A string BEGIN.
  A string END.
  An integer N representing the length of the DICT array.
  N space-separated strings denoting words in DICT.

Output:

For each test case, the output is a single integer indicating the length of the shortest transformation sequence from BEGIN to END. Output each test case result on a separate line.

Example:

# Example 1 Input:
2
hit
cog
5
hot dot dog lot log
hit
hot
2
hot cog

Output:

# Example 1 Output:
5
2

Constraints:

• 1 ≤ T ≤ 5
• 1 ≤ N ≤ 10²
• 1 ≤ |S| ≤ 10²
• All words have the same length.
• All transformations involve only lowercase English letters.
• BEGIN will not equal END.

Note:

Return -1 if no transformation sequence from BEGIN to END is possible. Implement the function, as printing is handled separately.