задача олимпиадная по информатике.Задача D. Автобусы Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по - вопрос №2666543

времени: 2 секунды Ограничение по памяти: 64 мегабайта Новый Президент Тридевятой республики начал свою деятельность с полной ревизии системы общественного транспорта страны. В результате на основе социологических опросов населения было составлено идеальное ежедневное расписание движения междугородних автобусов, утвержденное Парламентом республики. Более того, было решено заменить весь автобусный парк одинаковыми новыми, очень дорогими, но гораздо более надежными, красивыми и удобными машинами. Автобусная сеть страны охватывает N городов, занумерованных целыми числами от 1 до N. Идеальное расписание содержит M ежедневных рейсов, i-й рейс начинается в городе Fi в момент времени Xi и заканчивается в некотором другом городе Gi в момент времени Yi. Продолжительность каждого рейса ненулевая и строго меньше 24 часов. Рейс i выполняется одним из автобусов, находящихся в момент времени Xi в городе Fi. Новые автобусы не требуют ремонта и могут работать круглосуточно, поэтому автобус, прибывший в некоторый момент времени в некоторый город, всегда готов в тот же самый момент времени или позже отправиться в путь для обслуживания любого другого рейса из данного города.Автобус может выехать из города, только выполняя какой-либо рейс из расписания. Предполагается, что расписание будет действовать неограниченное время, поэтому может оказаться так, что его невозможно обслужить никаким конечным числом автобусов. Определите наименьшее количество новых автобусов, достаточное для обеспечения движения по расписанию в течение неограниченного периода времени. Формат входных данных В первой строке содержатся целые числа N и М (1 ⩽ N, M ⩽ 100 000) — количество городов и рейсов автобусов соответственно. ВкаждойизследующихMстроксодержитсяописаниерейсаавтобуса: номергородаотправления Fi, время отправления Xi, номер города назначения Gi (Fi ̸= Gi), время прибытия Yi, отделенные друг от друга одним пробелом. Времена задаются в формате HH:MM, где HH — часы от 00 до 23, MM — минуты от 00 до 59. Формат выходных данных В выходной файл выведите одно число — минимально необходимое количество автобусов. Если расписание невозможно обслуживать в течение неограниченного периода времени конечным числом автобусов, выведите число -1. Примеры стандартный ввод стандартный вывод 2 1 1 09:00 2 15:30 -1 5 5 1 09:00 2 14:30 3 23:45 1 06:50 2 14:30 3 20:50 4 09:00 5 21:00 5 10:00 4 20:00 3 Замечание Решения, верно работающие для N и М (1 ⩽ N, M ⩽ 10), будут набирать 35 баллов