Minimum Base Gene Sequence Length

You are given a set of gene differentiation rules and a list of genotype strings. Each rule is of the form \( L \to R \) (with \(|L| < |R|\)), indicating that a gene or gene‐sequence \(L\) can differentiate into the sequence \(R\). A genotype is said to be derivable if there exists a special base gene sequence \(S\) such that by repeatedly reversing the given rules (i.e. replacing an occurrence of \(R\) by \(L\)) you can obtain \(S\).

For every given genotype, determine whether it is derivable from some base gene sequence. If it is, output the minimum possible length of such an original sequence. (Note that if no reverse step is possible then the genotype itself is considered as a valid base sequence.)

Hint: You may solve the problem by reversing the production rules. For every occurrence of \(R\) in the current string, you can try replacing it by \(L\). Use recursion with memoization (or BFS) to explore all possible reductions, and take the minimum length among all outcomes.

inputFormat

The input begins with an integer \(R\) (the number of rules). The next \(R\) lines each contain two space‐separated strings representing a rule \(L\) and \(R\) (with \(|L| < |R|\)). Following that, an integer \(N\) is given representing the number of genotype queries. The next \(N\) lines each contain a nonempty genotype string.

Example:

1
A AA
2
AA
AAA

outputFormat

For each genotype, output a single integer on a separate line – the minimum length of a base gene sequence that can generate this genotype through a series of reverse rule applications.

If the genotype is not derivable by any sequence of rule reversals, output -1. (In our formulation, the genotype itself is always a valid candidate if no rule applies.)

sample

1
A AA
2
AA
AAA

1
1