Warp Speed#2624
In the not-so-distant future, space engineers may invent new technology for traveling through space, called a "warp drive." This warp drive allows a spaceship to travel faster than the speed of light by bending space and enabling the ship to cross that bent space in a single "hop." Since each hop takes an equal amount of time, the total travel time for any spaceship (equipped with a warp drive) depends on the number of hops. Engineers have also noticed that the distance of each hop is determined by certain types of force fields present in the area where the hop is made. To travel from the starting to the destination point, a spaceship may need to pass through many force fields, which could require multiple hops.
From their experiments, the following facts have been discovered:
The number of force field types is quite small.
Therefore, each force field type can be represented by a single English letter.
A spaceship can pass through any single force field in a single hop.
A spaceship can also pass through certain sequences of two or more force fields in a single hop. Such sequences are defined as single-hop-able rules.
An example list of these rules is shown in the following table.
In this example, there are rules, meaning a spaceship can pass through each using a single hop. The first rule is , which means the spaceship can pass through both and force fields in a single hop. The second is , which allows the ship to pass through , , , and in one hop.
Note that the sequence/rule does not exist in this example. So, although a ship can pass through the sequence, it cannot pass through in a single hop. It would need to make hops: the first to pass through , the second through the force field .
Goal
Suppose you are an engineer on a battle spaceship. Your task is to plot the fastest course for your spaceship through space. Your ship is equipped with a probe that can detect the sequence of force fields along the route to your destination. To fulfill your task, write a computer program that, according to the rules and any given sequence of force fields, finds the minimum number of hops.
The input is standard input and contains parts, separated by a blank line.
The first part is a set of single-hop-able sequence rules. The number of rules is between and .
Each line in the first part contains one rule.
Each rule is a (sub)sequence of force fields represented by a string of English letters (-, -).
The order in every (sub)sequence is left to right.
The length of any (sub)sequence is between and .
The second part is a set of force field sequences representing the paths a spaceship must traverse. The number of sequences is between and .
Each line in the second part contains one force field sequence.
Each sequence is represented by a string of English letters (-, -).
The order in each sequence is left to right.
The length of any sequence is between and .
A blank line after the second part marks the end of the input.
For each sequence in the second part, write output parts as follows:
The first line should contain the total number of solutions, followed by a space and the minimum number of hops.
In the following lines, write each solution on a separate line. Each solution is a space-separated sequence of substrings as given in the input, where a space is inserted between each hop subsequence. If there are multiple solutions, output them in ascending lexicographical (ASCII) order.
Additional Explanations
In the example, there are rules and input sequences.
- In the first sample output, there is solution with hops. The first hop uses the first rule. - In the second output, there is solution with hop using the second rule for the entire sequence. - In the third output, there are solutions with hops. The first solution uses the th rule; the second uses the rd rule. - In the fourth output, there are solutions with hops. The first solution applies the th rule twice. The second and third apply the rd and th rules in different positions. The last solution applies the rd rule twice. The last output is similar to the fourth, but the fifth rule is applied in the middle of the sequence.
Example 1