|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Жил был на свете в деревне Потемкино мальчик по имени Ратурбек,
сын Сергея. И он очень любил математику — правда, он предпочитал её
изобретать, а не учить в школе.
И вот однажды мальчик сел решать домашку, естественно,
посмотрев перед этим ответы в интернете.
Математика Ратурбека выглядит следующим образом: он может
путем какой-то операции (которая нас не интересует) преобразовать
число A в число B (оба в пределах тысячи). У него есть список длинной
N из возможных преобразований.
У мальчика есть входное число M и ему необходимо
(судя по ответу) получить число K, которое, к сожалению, не равно M.
Может ли Ратурбек сделать это в рамках своей математики, и если да
, то за какое минимальное число операций (ну а какой смысл писать
лишнее)?
Входные данные: Первая строка содержит целое число
M (0 ≤ m ≤ 1000) – количество математических
преобразований. Каждая из последующих M строк описывает одно
преобразование и имеет формат «число A» -> «число B», где число А
– исходное число, число B – число, полученное в результате
преобразования. M+2-ая строка входного содержит начальное число,
M+3-ая – число, которое необходимо получить.
Выходные данные: Натуральное число - минимальное
количество математических операций, которое требуется для
получения требуемого числа из исходного, или -1, если требуемое
число невозможно получить.
Пример входных данных:
Ввод: |
Вывод: |
5
5 -> 7
7 -> 41
7 -> 66
6 -> 9
7 -> 9
5
9 |
2 |
Для отправки решений необходимо выполнить вход.
|