Вы должны помочь будущему художнику Винсенту ван Динскому смешать цвета для своих картин. Учитель дал Винсенту книгу, содержащую правила смешения цветов, а также цветовую палитру, и попросил его получить набор цветов, необходимый для написании картины. Винсенту придется экспериментировать, пока он не найдет минимальное количество цветовых смесей, необходимых для получения каждого цвета в картине.
Примечания:
все названия цветов используют символы a-z 0-9 (нижний регистр)
a color mixing rule is made by three colors written on the same line, meaning "color1 mixed with color2 gives color3" – e.g. "yellow cyan green"
mr. van Dinsky is not willing to do random color mixing experiments – if he doesn’t find in the book what is the result of mixing yellow with green, he will never attempt to do this operation. He is also very bad at logic inference – e.g. if the book says that yellow+cyan=green, yellow+magenta=red and red+cyan=black, he will not assume that green+magenta=black (unless the book explicitly tells what is the result of mixing green magenta). On the other hand – he is fully aware that it doesn’t matter what color you start with – mixing yellow green is the same as mixing green yellow.
Содержит данные в следующем порядке:
все правила смешения цветов в книге
пустая строка
один или несколько тестов, каждый из которых состоит из двух строк:
все доступные цвета изначально находятся на палитре
все цвета, необходимые для написания картины
You should produce an output that contains one line for each painting (i.e. each data set); on that line, for each color in the painting, the minimum number of color mixes that will produce the desired color (starting from the colors available initially on the palette; the result is '-1' if it’s impossible to obtain the desired color).
You can assume that the input is correct, there are less than 50000 color mixing rules in the rule book and less than 1000 colors.