Gigantic Reactions
British scientists are working on a secret research. They found new, very reactive atoms that
can transform anytime, in any circumstances. Right now, they are performing a simulation to
form a more exact picture of the atoms. A sequence of atoms in different states is
represented by a string. Atoms in the string are separated by '+'
characters,
and the state of an atom is represented by an arbitrary nonempty string that contains no
'+'
characters. The same string always represents the same state. It has
already been observed that the order of the atoms never change. The scientists have also
determined what transformations the atoms can go through. We know that in one step, they can
transform from all states to at most one other state. Any element of a sequence can
transform at any moment, and it cannot be predicted how many atoms will react at a time.
Input Specification
The first line of the input contains a string in the form
S_{1}[+
S_{2}]…, describing the current
state of the sequence. The next line consists of a positive integer N, which is the
number of the possible state transformations
(1 ≤ N ≤ 10). This line is followed by N
lines in the form X Y, where X is a state of an atom that can
transform to state Y at any moment. You may safely assume that there are no cycles in
the transformations and that all X values occur only once in the input.
Output Specification
The program should print in the first line of the output the number of different states that
may occur if the particles start to react. Each of the following lines should contain exactly
one possible state. The states should appear in lexicographic order of the strings
representing the states. The state in the input should not appear in the output!
Sample Input
a1+a2+b2
3
a1 a0
a2 a1
b2 b0
download as text file
Output for Sample Input
12
a0+a0+b0
a0+a0+b2
a0+a1+b0
a0+a1+b2
a0+a2+b0
a0+a2+b2
a1+a0+b0
a1+a0+b2
a1+a1+b0
a1+a1+b2
a1+a2+b0
download as text file