|
Участок железной дороги проходит через станции, пронумерованные от 1 до N. Из
расписания движения поездов известно, какой поезд на какой станции делает остановку
Требуется определить, за какое минимальное время можно добраться от станции с номером
1 до станции с номером Р, и количество сделанных пересадок. Если есть несколько вариантов
с минимальным временем, то из них выбирается вариант с минимальным числом пересадок.
Input
Во входном файле записаны сначала числа: N (2 <= N <=100) и P (2 <= Р <= N). Затем
записано число M (0 <= M <= 100), обозначающее количество рейсов поездов. Далее идет
описание M рейсов поездов. Описание каждого рейса начинается с числа Ki (2 <= Ki <= N) —
количества станций, на которых поезд останавливается, а далее следует Ki пар чисел, первое число
каждой пары задает номер станции, второе — время, когда поезд останавливается на этой станции
(время выражается целым числом из диапазона от 0 до 10^9). Станции внутри одного рейса
упорядочены в порядке возрастания времени. В течение одного рейса поезд все время движется в
одном направлении — либо от станции 1 в сторону станции N, либо в обратном направлении.
Пассажир приходит на 1-ю станцию в момент времени 0.
Output
В выходной файл выведите два числа (по одному в строке) — минимальное время, за
которое можно добраться от станции 1 до станции Р, и количество пересадок. Если
существующими рейсами поездов это сделать невозможно, выведите -1.
Примечание 1. Красным цветом выделено дополнение, которого не было в оригинальной задаче
Примечание 2. Тесты не оригинальные
Sample
| Input | Output |
|---|
Пример 1. Вход:
5 3
4
2 1 5 2 10
2 2 10 4 15
4 5 0 4 17 3 20 2 35
3 1 2 3 40 4 45
| Пример 1. Выход:
20
2
|
| 