A gene is a string over the characters A, C, G, T. Starting from start, you may change one character at a time. Every intermediate gene (and the final end gene) must appear in the given bank of valid genes. Find the minimum number of single-character mutations to transform start into end. If it is impossible, output -1.
If start equals end, zero mutations are needed.
Input format
Line 1: the start gene.
Line 2: the end gene.
Line 3: an integer B, the number of genes in the bank.
Next B lines: the bank genes (same length as start).
Output format
One line: the minimum number of mutations, or -1 if unreachable.
Constraints
- 1 <= gene length <= 10
- 0 <= B <= 200
- All genes consist of the characters A, C, G, T.