Minimum String Transformations

You are given several datasets, each containing a start string, an end string, and a set of allowed character transformations. In one transformation step, you can replace a character in the current string by one of its allowed transformations. Your task is to compute the minimum number of steps required to transform the start string into the end string. If the transformation is not possible, output -1.

The transformation rules are defined as pairs \( (a, b) \) meaning that the character \( a \) can be replaced by the character \( b \). For each dataset, perform a breadth-first search (BFS) on the state space where each state is a string obtained by applying valid transformations. Return the minimum steps needed to reach the end string from the start string.

Note: Only characters that differ between the current string and the target string are considered for transformation at each step.

inputFormat

The first line contains an integer \(T\) indicating the number of datasets. Each dataset is described as follows:

• The first line of a dataset contains the start string, the end string, and an integer \(n\) representing the number of transformation rules, separated by spaces.
• Each of the next \(n\) lines contains two space-separated characters \(a\) and \(b\) indicating that character \(a\) can be transformed into character \(b\).

You need to process all \(T\) datasets.

outputFormat

For each dataset, output a single line containing an integer: the minimum number of transformation steps required to convert the start string into the end string, or \(-1\) if it is not possible.

## sample

2
abc def 3
a d
b e
c f
xyz foo 2
x m
y n

3
-1

</p>