Van Dinsky's Color Mixing

Vincent van Dinsky wants to be a painter, and he mixes the paint for his pictures himself. His master handed him a book of color mixing rules and a palette, and told him to produce every color a picture needs with as few mixing steps as possible.

Color names use only the lowercase letters a to z and the digits 0 to 9.

One rule is three color names on a single line. yellow cyan green means that yellow mixed with cyan gives green. The order does not matter, so van Dinsky treats mixing yellow into cyan and cyan into yellow as the same thing. He never tries a combination the book does not list. If the book says nothing about yellow mixed with green, he will not run that experiment. He also draws no conclusions of his own. Even with yellow plus cyan gives green, yellow plus magenta gives red and red plus cyan gives black in the book, he does not guess that green plus magenta gives black. A rule counts only when the book states it.

Every mixing step consumes one portion of each of the two ingredient colors and yields one portion of the result. A color on the palette can be taken as often as he likes and does not count as a mixing step. A portion produced by mixing is used up once, so a color needed twice as an ingredient has to be mixed twice.

The cost $\mathrm{cost}(c)$ of a color $c$ is therefore defined like this. It is $0$ when $c$ is on the palette. Otherwise it is the smallest value of $\mathrm{cost}(a) + \mathrm{cost}(b) + 1$ over every rule saying that $a$ mixed with $b$ gives $c$. When no such value exists, $c$ cannot be produced.

The first part of the input is the rule book. Each line holds three color names separated by spaces. One empty line follows the rule book. When there is no rule at all, the input starts with that empty line.

After the empty line come one or more painting tasks, each of them two lines.

• The first line holds the colors on the palette at the start, separated by spaces.
• The second line holds the colors the picture needs, separated by spaces.

Both lines hold at least one color. The book holds fewer than 50000 rules, and fewer than 1000 distinct colors appear in the input.

Print one line per painting task. On that line print, for each color the picture needs and in the given order, the minimum number of mixing steps that produces one portion of that color starting from the palette, separated by spaces. Print -1 for a color that cannot be produced.