String Transformation Challenge

Given two strings \( A \) and \( B \) and up to 6 transformation rules, determine the minimum number of operations required to transform \( A \) into \( B \) using these rules.

Each transformation rule is described in the form:

• \( A_i \to B_i \)

This means that in one operation, you can select one occurrence of the substring \( A_i \) in the current string and replace it with \( B_i \). You may use the rules in any order and any number of times. If it is impossible to transform \( A \) into \( B \), output -1.

Example:

Let \( A = \texttt{abcd} \), \( B = \texttt{xyz} \), and the rules be:

• \( \texttt{abc} \to \texttt{xu} \)
• \( \texttt{ud} \to \texttt{y} \)
• \( \texttt{y} \to \texttt{yz} \)

The transformation sequence can be:

1. \( \texttt{abcd} \to \texttt{xud} \) (applying rule \( \texttt{abc} \to \texttt{xu} \))
2. \( \texttt{xud} \to \texttt{xy} \) (applying rule \( \texttt{ud} \to \texttt{y} \))
3. \( \texttt{xy} \to \texttt{xyz} \) (applying rule \( \texttt{y} \to \texttt{yz} \))

Total operations = 3.

inputFormat

The input consists of multiple lines:

1. First line: the initial string \( A \).
2. Second line: the target string \( B \).
3. Third line: an integer \( n \) representing the number of transformation rules (\( 1 \leq n \leq 6 \)).
4. Next \( n \) lines: each line contains two non-empty substrings separated by a space, representing a transformation rule \( A_i \) and \( B_i \) respectively.

It is guaranteed that all strings contain only printable characters and have reasonable lengths.

outputFormat

Output a single integer: the minimum number of operations required to transform \( A \) into \( B \). If it is impossible, output -1.

sample

abcd
xyz
3
abc xu
ud y
y yz

3