Рус Uzb Eng

C17B. Сережа и контесты
Ограничение по времени: 2 cекунды
Ограничение по памяти: 64 мегабайт

Сережа — программист, поэтому он очень любит участвовать в раундах Codesorfes. Но поскольку в Ужляндии интернет не очень хороший, иногда Сережа пропускает раунды.
На Codesorfes бывают раунды двух типов: Div1 (для более опытных участников) и Div2 (для новичков). Иногда два раунда Div1 и Div2 проводятся синхронно (при этом Div1 раунды не проводятся без Div2), в остальных случаях раунды не пересекаются по времени. Каждый раунд имеет свой уникальный идентификатор — целое положительное число. Раунды нумеруются идентификаторами последовательно (без пропусков) по времени проведения. Идентификаторы раундов, которые проводятся синхронно, отличаются на единицу, при этом идентификатор Div1 раунда всегда больше.
Сережа — новичок, он может участвовать только в раундах типа Div2. На данный момент он участвует в Div2 раунде, идентификатор которого равен x. Сережа точно помнит, что он участвовал в ровно k раундах до этого раунда. Также он помнит все идентификаторы раундов, в которых он участвовал, и раундов, которые шли синхронно с последними. Про пропущенные раунды Сережа не помнит ровным счетом ничего. Сережа очень хочет знать, какое минимальное и какое максимальное количество Div2 раундов он мог пропустить? Помогите ему найти эти два числа.

Входные данные:
В первой строке записано два целых числа: x (1 <= x <= 4000) — раунд, в котором сейчас участвует Сережа, и k (0 <= k < 4000) — количество раундов, в которых он участвовал ранее. Ниже в k строках даны описания раундов, в которых Сережа участвовал ранее. Если Сережа участвовал в синхронном раунде, то соответствующая строка имеет вид: «1 num2 num1» (где num2 — идентификатор этого Div2 раунда, num1 — идентификатор синхронного Div1 раунда). Гарантируется, что num1 - num2 = 1. Если Сережа участвовал в обычном Div2 раунде, то соответствующая строка имеет вид: «2 num» (где num — идентификатор этого Div2 раунда). Гарантируется, что номера всех заданных раундов меньше x.

Выходные данные:
Выведите в единственной строке два целых числа — минимальное и максимальное количество раундов, которые Сережа мог пропустить.

Пример ввода Пример вывода
3 2
2 1
2 2
9 3
1 2 3
2 8
1 4 5
0 0



2 3
Область:
Источник задачи:

Отправить решение на проверку

Design by TUIT © 2012-2017 TUIT Online Judge. All rights reserved.