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₁[+S₂]…, 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

1. a1+a2+b2
2. 3
3. a1 a0
4. a2 a1
5. b2 b0

download as text file

Output for Sample Input

1. 12
2. a0+a0+b0
3. a0+a0+b2
4. a0+a1+b0
5. a0+a1+b2
6. a0+a2+b0
7. a0+a2+b2
8. a1+a0+b0
9. a1+a0+b2
10. a1+a1+b0
11. a1+a1+b2
12. a1+a2+b0

download as text file