Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Алхимия

Первоисточник: North East European Regional Coltest

URL первоисточника: http://neerc.ifmo.ru/

Задачу добавил: toto

Успешно сдано решений: 11

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 2 секунды


Ограничение по памяти: 64 мегабайта


Алхимки Средневековья владели знаниями о превращении различных химических веществ друг
в друга. Это подтверждают и недавние исследования археологов.
В ходе археологических раскопок было обнаружено m глиняных табличек, каждая из которых
была покрыта непонятными на первый взгляд символами. В результате расшифровки выяснилось, что
каждая из табличек описывает одну алхимическую реакцию, которую умели проводить алхимики.
Результатом алхимической реакции является превращение одного вещества в другое. Заданы
набор алхимических реакций, описанных на найденных глиняных табличках, исходное вещество и
требуемое вещество. Необходимо выяснить, возможно ли преобразовать исходное вещество в требу-
емое с помощью этого набора реакций, а в случае положительного ответа на этот вопрос - найти
минимальное количество реакций, необъодимое для осуществления такого преобразования.

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

Первая строка входного файла содержит целое число m (0 <= m <= 1000) - количество записей в книге.
Каждая из последующих m строк описывает одну алхимическую реакцию и имеет формат
вещество1 -> вещество2, где вещество 1 - название исходного вещества, вещество 2 - на-
звание продукта алхимической реакции.
m+2-ая строка входного файла содержит название вещества, которое имеется исходно, m+3-ая - название вещества, которое требуется получить.
Во входном файле упоминается не более 100 различных веществ. Название каждого из веществ
состоит из строчных и заглавных латинских букв и имеет длину не более 20 символов. Строчные и
заглавные буквы различаются.

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

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


Тестовые примеры


input.txt

5
Aqua -> AquaVita
AquaVita -> PhilosopherStone
AquaVita -> Argentum
Argentum -> Aurum
AquaVita -> Aurum
Aqua
Aurum
output.txt

2

input.txt
5
Aqua -> AquaVita
AquaVita -> PhilosopherStone
AquaVita -> Argentum
Argentum -> Aurum
AquaVita -> Aurum
Aqua
Osmium

output.txt
-1

Сдать задачу

Задать вопрос жюри по этой задаче