Новый алхимик ≡

Условие

Счастливый день! могу сегодня я
В шестой сундук (сундук еще не полный)
Горсть золота накопленного всыпать.
Немного, кажется, но понемногу
Сокровища растут.
А. С. Пушкин

Алхимик Петя изобрел философский камень, с использованием которого можно проводить некоторое множество алхимических реакций по превращению одних веществ в другие. Масса каждого вещества, вступающего в реакцию, и масса каждого образующегося в результате реакции вещества составляет ровно один грамм. Естественно, закон сохранения массы при этом может нарушаться.

Изначально у Пети имеется один грамм свинца. С помощью философского камня Петя может превратить свой свинец в другие вещества, на которые он потом также сможет воздействовать философским камнем. Выполняя одну за другой алхимические реакции, Петя стремится получить как можно больше золота.

Требуется написать программу, определяющую по заданному описанию алхимических реакций, выполняемых философским камнем, наибольшее количество золота, которое может получить Петя.

Формат входного файла

В первой строке записано целое число K — количество различных веществ, участвующих и образующихся в алхимических реакциях. Вторая строка содержит список этих веществ, разделенных пробелом (в списке обязательно есть свинец и золото). Названия веществ не длиннее 10 букв.

В третьей строке записано целое число L — количество типов реакций, выполняемых философским камнем. Далее в файле идут L описаний этих реакций. Каждое описание реакции состоит из двух строк:

• в первой строке — названия веществ, вступающих в реакцию,
• во второй строке — названия веществ, получающихся в результате реакции.

Формат выходного файла

Ваша программа должна вывести в выходной файл либо одно целое число — искомое количество граммов золота, либо сообщение QUANTUM SATIS, если Петя может получить любое количество золота.

Внимание! Вместо 'QUANTUM SATIS' следует выводить число -1.

Ниже приведены примеры входного и выходного файлов для представленных на рисунке алхимических реакций, выполняемых философским камнем.

Ограничения

Примеры тестов

5
свинец золото сера ртуть медь
5
свинец
золото сера ртуть
свинец
золото медь ртуть
ртуть золото
сера
ртуть медь
ртуть сера золото
сера ртуть
золото

3