ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат Урала 2010

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

I. Утро депутата

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В Екатеринбурге ровно n автобусных остановок и m маршрутов. Транспортная система спроектирована так, что расстояние между двумя соседними остановками любой автобус проезжает ровно за одну минуту. Каждый автобус запускает пассажиров на первой остановке своего маршрута не раньше семи утра. Движение по маршруту начинается только в целое количество минут, причём два автобуса не могут одновременно отправиться на один и тот же маршрут. Когда автобус доезжает до последней остановки своего маршрута, он не разворачивается и не едет назад. Никакого расписания движения автобусов в Екатеринбурге нет и в помине, и автобусы могут ездить как угодно с учётом описанных ограничений.
Депутат Екатеринбургской городской Думы Леонид решил поставить общественный транспорт под контроль граждан. В 06:50 он вышел на ближайшую к его дому автобусную остановку с блокнотом наизготовку. Он пообщался с людьми, стоящими на остановке, и те рассказали ему, как в Екатеринбурге принято ездить на автобусах. Все, кто хочет влезть в свой автобус, выходят на остановки заранее — к 06:59 утра. Жители очень торопятся на работу, поэтому высадка и посадка пассажиров происходит мгновенно. Любой пассажир выбирает автобус, в который ему нужно сесть, по следующему алгоритму:
  • Если к остановке подъехал автобус, который довезёт пассажира до нужной остановки, он садится на него;
  • Если к остановке одновременно подъехало несколько подходящих автобусов, то пассажир садится на тот, который довезёт его до нужной остановки раньше;
  • Если и таких автобусов подъехало несколько, то пассажир садится на автобус с минимальным номером маршрута.
Ровно в семь утра Леонид начал записывать номера маршрутов останавливающихся автобусов и время их остановки. Толпа на остановке понемногу уменьшалась. Леонид уже начал получать удовольствие от процесса, как вдруг вспомнил, что ему самому пора на заседание комиссии по спортивному программированию. Тогда он заскочил в подошедший автобус. Там уже было сорок два человека, а помимо Леонида в автобус зашли ещё тринадцать человек. Помогите ему посчитать, какое минимальное и максимальное количество из этих людей может находиться в автобусе, когда он подъедет к нужной Леониду остановке.

Исходные данные

В первой строке через пробел записаны целые числа n и m (3 ≤ n, m ≤ 100) — количество остановок и автобусных маршрутов в Екатеринбурге. В i-й из следующих m строк описан маршрут номер i. Маршрут задаётся последовательностью попарно различных целых чисел от 1 до n — номерами остановок, через которые он проходит. Каждый маршрут проходит не менее чем через две остановки. Список заканчивается числом −1. Числа в списке разделены одним пробелом. Леонид живёт около остановки номер 1 и собирается выйти из автобуса на остановке номер 2.
В следующей строке записано целое число k (1 ≤ k ≤ 100) — количество автобусов, которые зафиксировал в своём блокноте Леонид. Далее следуют k строк, в каждой из которых через пробел записано время появления автобуса на остановке Леонида в формате hh:mm (07 ≤ hh ≤ 23; 00 ≤ mm ≤ 59) и номер маршрута этого автобуса. Записи в блокноте упорядочены по времени. Последним в списке указан номер маршрута автобуса, на который сел Леонид. Известно, что он успел записать информацию обо всех автобусах, пришедших на его остановку одновременно с тем автобусом, на котором он уехал. Гарантируется, что Леонид сел на автобус, который довезёт его до остановки номер 2, а остановка номер 1 не является в соответствующем маршруте первой.

Результат

Выведите через пробел два числа — минимальное и максимальное количество людей, которые составят компанию Леониду на всём пути от остановки номер 1 до остановки номер 2.

Пример

исходные данныерезультат
4 3
1 4 -1
4 1 -1
3 1 4 2 -1
2
07:00 1
07:10 3
13 55
Автор задачи: Алексей Самсонов
Источник задачи: XIV чемпионат Урала по спортивному программированию, 10 апреля 2010 г.
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1771. Утро депутата