Урпал живет в большом городе. Он назначил свидание своей любимой этим вечером.
Всего в городе n перекрестков, пронумерованных от 1 до n. Перекрестки соединены m направленными улицами, все улицы имеют одинаковую длину. Урпал живет на перекрестке a, а свидание назначено в ресторане на перекрестке b. Он хочет добраться до перекрестка b на общественном транспорте. Всего есть k автобусных компаний. В начале каждой секунды автобус из i-ой компании выбирает случайный наикратчайший путь между перекрестком si и перекрестком ti и проезжает по этому пути. Возможна такая ситуация, когда от перекрестка si до перекрестка ti не существует никакого пути. В этом случае ни один автобус не отправится из si до ti. Если автобус проезжает перекресток, на котором стоит Урпал, то юноша может сесть на этот автобус. Также он может сойти с автобуса на любом перекрестке на пути.
Урпал хочет знать, возможно ли добраться до свидания на общественном транспорте за конечное время (время его поездки — это сумма длин дорог, которые он проехал) и на какое наименьшее количество автобусов ему придется сесть в наихудшем случае.
В любой момент времени юноша знает лишь только свое местоположение и место, куда ему надо ехать. Когда он садится в автобус, он знает только номер компании этого автобусного маршрута. Конечно же, Урпал хорошо знает карту города и маршруты (пары si, ti) для каждой компании.
Обратите внимание, что Урпалу неизвестна скорость автобусов.
Выходные данные
В единственной строке выходных данных выведите наименьшее количество автобусов, на которые Урпал должен сесть по пути на свидание в наихудшем случае. Если в нахудшем случае пункт назначения достичь невозможно, выведите -1.