Задача №3341. Алихмия (CD)
Алхимики Средневековья владели знаниями о превращении различных химических веществ друг в друга. Это подтверждают и недавние исследования археологов. В ходе археологических раскопок было обнаружено m глиняных табличек, каждая из которых была покрыта непонятными на первый взгляд символами. В результате расшифровки выяснилось, что каждая из табличек описывает одну алхимическую реакцию, которую умели проводить алхимики. Результатом алхимической реакции является превращение одного вещества в другое. Заданы набор алхимических реакций, описанных на найденных глиняных табличках, исходное вещество и требуемое вещество. Необходимо выяснить, возможно ли преобразовать исходное вещество в требуемое с помощью этого набора реакций, а в случае положительного ответа на этот вопрос — найти минимальное количество реакций, необходимое для осуществления такого преобразования.
Первая строка входного файла содержит целое число \(m\) (\(0 \leq m \leq 1000\)) — количество записей в книге. Каждая из последующих \(m\) строк описывает одну алхимическую реакцию и имеет формат вещество1->вещество2, где вещество1 — название исходного вещества, вещество2 — название продукта алхимической реакции. m+2-ая строка входного файла содержит название вещества, которое имеется исходно, m+3-ая — название вещества, которое требуется получить. Во входном файле упоминается не более 100 различных веществ. Название каждого из веществ состоит из строчных и заглавных латинских букв и имеет длину не более 20 символов. Строчные и заглавные буквы различаются.
В выходной файл выведите минимальное количество алхимических реакций, которое требуется для получения требуемого вещества из исходного, или -1, если требуемое вещество невозможно получить.
5 Aqua -> AquaVita AquaVita -> PhilosopherStone AquaVita -> Argentum Argentum -> Aurum AquaVita -> Aurum Aqua Aurum
2
5 Aqua -> AquaVita AquaVita -> PhilosopherStone AquaVita -> Argentum Argentum -> Aurum AquaVita -> Aurum Aqua Osmium
-1