Алхимия
Первоисточник: 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