eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Кактус

Кактус

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

prb5351

Кактусность первого графа на рисунке равно 35. Второй граф не является кактусом, так как ребро (2, 3) лежит на двух циклах. Третий граф не является кактусом, так как он несвязный.

Входные данные

Первая строка содержит два целых числа n и m (1n20000, 0m1000). Здесь n - количество вершин в графе. Вершины пронумерованы от 1 до n. Ребра графа представлены множеством реберно непересекающихся путей, где m - количество таких путей.

Каждая из следующих m строк содержит путь в графе. Путь начинается с целого числа k[i] (2k[i]1000), за которым следует k[i] целых чисел от 1 до n. Эти k[i] чисел задают вершины пути. Путь может проходить по одной вершине несколько раз, но каждое ребро будет задано лишь один раз во всех входных данных. Граф не содержит мультиребер (между парой вершин находится не более одного ребра).

Выходные данные

Выведите одно число - кактусность графа. Отметим, что кактусность может быть большим числом.

Пример

Входные данные #1
14 3
9 1 2 3 4 5 6 7 8 3
7 2 9 10 11 12 13 10
2 2 14
Выходные данные #1
35
Источник 2005 ACM NEERC, Semifinals, November 30, Problem C