Кактус
Кактус — це зв'язний неорієнтований граф, у якому кожне ребро належить не більше ніж одному циклу. Інтуїтивно, кактус є узагальненням дерева, де дозволені деякі цикли. Вам потрібно перевірити, чи є заданий граф кактусом. Важлива відмінність кактуса від дерева полягає в тому, що кактус може містити кілька остовних підграфів, які також є кактусами. Кількість таких підграфів (включаючи сам граф) визначає кактусність графа (для дерева це число дорівнює одиниці). Кактусність графа, що не є кактусом, дорівнює нулю.
Кактусність першого графа на рисунку дорівнює 35. Другий граф не є кактусом, оскільки ребро (2, 3) належить двом циклам. Третій граф не є кактусом, оскільки він незв'язний.
Вхідні дані
Перша строка містить два цілі числа n і m (1 ≤ n ≤ 20000, 0 ≤ m ≤ 1000). Тут n — кількість вершин у графі. Вершини пронумеровані від 1 до n. Ребра графа представлені множиною реберно неперетинних шляхів, де m — кількість таких шляхів.
Кожен з наступних m рядків містить шлях у графі. Шлях починається з цілого числа k[i] (2 ≤ k[i] ≤ 1000), за яким слідує k[i] цілих чисел від 1 до n. Ці k[i] числа задають вершини шляху. Шлях може проходити через одну вершину кілька разів, але кожне ребро буде задано лише один раз у всіх вхідних даних. Граф не містить мультиребер (між парою вершин знаходиться не більше одного ребра).
Вихідні дані
Виведіть одне число — кактусність графа. Зазначимо, що кактусність може бути великим числом.