Məsələlər
Warp Speed
Warp Speed
In the not-so-distance future, space engineers can invent a new technology for traveling through space and name it as "warp-drive". This warp-drive can make a spaceship travel faster than light speed. It works by bending an amount of distance in space and make a ship travel through that bended space in a single "hop". And since the time spent for each hop is equal, the total traveling time for any spaceship (that is equipped with this warp-drive) depends on the number of hops it make. Moreover, these engineers notice that distance of a hop depends on some kind of force fields in the space where that hop is operated. To travel from a beginning to an ending point, a spaceship may have to pass through many force fields, which may make that spaceship hop so many times.
And from their experiments, they found some facts as follow.
\begin{itemize}
\item A number of force field types is quite small.
\begin{itemize}
\item So one English character can be used to name each of these force filed types.
\end{itemize}
\item A spaceship can pass through every single force field in a single hop.
\item A spaceship can pass through a certain sequences of two or more force fields in a single hop. And these certain sequences are kept as rules of single-hop-able sequences.
\begin{itemize}
\item An example of list of these rules is shown as in the following table.
\end{itemize}
\end{itemize}
\begin{itemize}
\item \begin{itemize}
\item In this example, there are \textbf{4} rules, which means that a spaceship can pass through each of them using a single hop. The first one is "\textbf{ab}", which means that a spaceship can pass through '\textbf{a}' and '\textbf{b}' force field in a single hop. The second one is "\textbf{abcd}" which means that it can pass through '\textbf{a}', '\textbf{b}', '\textbf{c}' and '\textbf{d}' in one hop.
\item Please be notified that there is no "\textbf{abc}" sequence/rule in this example, so even though the ship can pass through "\textbf{abcd}" sequence, it is unable to pass through "\textbf{abc}" (in a single hop). It has to make \textbf{2} hops, the first hop is to pass through "\textbf{ab}" sequence and the second hop is to pass through "\textbf{c}" force field.
\end{itemize}
\end{itemize}
\textbf{Goal}
Suppose that you are an engineer on a battle spaceship. Your duty is to drive your spaceship through space as fast as possible. Your spaceship has a probe device that can identify a sequence of force fields along the path to your destination. In order to accomplish your duty, you have to build a computer program to find the minimum hop based on rules and any given sequences of force fields.
\InputFile
Input is standard inputs which contain \textbf{2} parts of data which are separated by a blank line.
The first part is a set of rules of single-hop-able sequences. The number of rules is between \textbf{1} and \textbf{10000}.
\begin{itemize}
\item Each line in this first part contains one rule.
\item Each rule is a (sub)sequence of force fields specified by a string of alphabets (\textbf{a-z}, \textbf{A-Z}).
\item The order in every (sub)sequence is from left to right.
\item The size of any (sub)sequence is between \textbf{2} and \textbf{20}.
\end{itemize}
The second part is a set of force fields along path that a spaceship has to pass through. The number of sequence is between \textbf{1} and \textbf{200}.
\begin{itemize}
\item Each line in this second part contains one sequence of force field in one path.
\item Each sequence is specified by a string of alphabets (\textbf{a-z}, \textbf{A-Z}).
\item The order in every sequence is from left to right.
\item The size of any sequence is between \textbf{2} and \textbf{500}.
\end{itemize}
The blank line after the second part is the termination of the input.
\OutputFile
For each sequence in the second part of input, write \textbf{2} parts of output as follows
\begin{itemize}
\item In the first line, write the total number of solutions followed by a space and the number of minimum hops.
\item In the following lines, write each of the solutions in each line. Each solution contains a sequence of force fields as given in the input, where a space is inserted between each hop sub sequences. If there are two or more solutions, they must be sorted by ascending and lexicographical (ASCII) order.
\end{itemize}
\textbf{More Explanations}
There are \textbf{5} rules and \textbf{5} input sequences in this sample input.
In the first sample output, there is 1 solution with \textbf{2} hops. The first hop is from the first rule.
In the second output, there is \textbf{1} solution with \textbf{1} hop using the second rule for the whole sequence.
In the third output, there are \textbf{2} solutions with \textbf{2} hops. Its first solution is from the \textbf{4}^th rule and the second solution is from the \textbf{3}^rd rule.
In the fourth output, there are \textbf{4} solutions with \textbf{4} hops. The first solution is applied using the \textbf{4}^th rule twice. The second and third is applied using the \textbf{3}^rd and \textbf{4}^th rules in different position.
The last solution is applied using the \textbf{3}^rd rules twice The last output is quite similar to the fourth one, but it is also applied with the fifth rule in the middle of the sequence.
Giriş verilənləri #1
ab abcd abd bde CgeF abc abcd abde abdeabde abdeCgeFabde
Çıxış verilənləri #1
1 2 ab c 1 1 abcd 2 2 a bde abd e 4 4 a bde a bde a bde abd e abd e a bde abd e abd e 4 5 a bde CgeF a bde a bde CgeF abd e abd e CgeF a bde abd e CgeF abd e