Урпал живет в большом городе. Он назначил свидание своей любимой этим вечером.

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

Урпал хочет знать, возможно ли добраться до свидания на общественном транспорте за конечное время (время его поездки — это сумма длин дорог, которые он проехал) и на какое наименьшее количество автобусов ему придется сесть в наихудшем случае.

В любой момент времени юноша знает лишь только свое местоположение и место, куда ему надо ехать. Когда он садится в автобус, он знает только номер компании этого автобусного маршрута. Конечно же, Урпал хорошо знает карту города и маршруты (пары s_i, t_i) для каждой компании.

Обратите внимание, что Урпалу неизвестна скорость автобусов.