Десятиріччя кактусів#7563

Десятиріччя кактусів

1 секунда

64 мегабайти

Дуже складна

Це $20$ -ті змагання Північно-Східного Європейського регіону (NEERC). Задачі на кактуси стали традицією NEERC. Перша задача про кактуси була в $2005$ році, тому сьогодні десятиріччя кактусів.

Кактус — це зв'язний неорієнтований граф, у якому кожне ребро належить не більш ніж одному простому циклу. Інтуїтивно кактус — це узагальнення дерева, в якому дозволено деякі цикли. Мультиребра (кілька ребер між парою вершин) і петлі (ребра, що з'єднують вершину із самою собою) у кактусі не дозволені.

Вам задано кактус. Давайте перемістимо ребро — видалимо з графа одне ребро і з'єднаємо ребром іншу пару вершин так, щоб граф залишився кактусом. Скільки існує варіантів таких переміщень ребер?

Наприклад, у лівому верхньому кактусі (заданому в першому прикладі) існує $42$ варіанти переміщення ребра. У правому кактусі (заданому в другому прикладі), який є класичним прикладом кактуса ще з NEERC $2005$ року, існує рівно $216$ варіантів переміщення ребра.

Вхідні дані

Перший рядок містить два цілих числа $n$ і $m$ ( $1 \leq n \leq 50000$ 1 \leq n \leq 50000, $0 \leq m \leq 50000$ 0 \leq m \leq 50000). Тут $n$ — кількість вершин у графі. Вершини пронумеровані з $1$ до $n$ . Ребра задані множиною реберно-неперетинних шляхів, де $m$ — кількість таких шляхів.

Кожен із наступних $m$ рядків містить шлях у графі. Шлях починається числом $k_{i}$ k_i ( $2 \leq k_{i} \leq 1000$ 2 \leq k_i \leq 1000), за яким слідують $k_{i}$ k_i цілих чисел від $1$ до $n$ . Ці $k_{i}$ k_i числа представляють вершини графа у шляху. Сусідні вершини у шляху різні. Шлях може проходити через одну вершину декілька разів, але кожне ребро з'являється лише один раз у всьому вводі.

Граф у вводі є кактусом.

Вихідні дані

Виведіть одне число — кількість варіантів перемістити ребро у кактусі.

Приклади

Приклад 1

Приклад 2