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