Ювілей кактуса
Це 20-те змагання Північно-Східного Європейського регіону (NEERC). Завдання на кактуси стали традицією NEERC. Перше завдання про кактуси було в 2005 році, тому сьогодні ювілей - 10-річчя кактуса.
Кактус - це зв'язний неорієнтований граф, у якому кожне ребро належить не більше ніж одному циклу. Інтуїтивно, кактус - це узагальнення дерева, в якому дозволені деякі цикли. Мультиребра (кілька ребер між парою вершин) і петлі (ребра, що з'єднують вершину із самою собою) в кактусі не дозволені.
Вам задано кактус. Давайте перемістимо ребро - видалимо з графа одне ребро і з'єднаємо ребром іншу пару вершин так, щоб граф залишився кактусом. Скільки існує варіантів таких переміщень ребер?
Наприклад, у лівому кактусі зверху (заданому в першому прикладі) існує 42 варіанти переміщення ребра. У правому кактусі (заданому в другому прикладі), який є стандартним прикладом кактуса ще з NEERC 2005 року, існує точно 216 варіантів переміщення ребра.
Вхідні дані
Перший рядок містить два цілих числа n і m (1 ≤ n ≤ 50 000, 0 ≤ m ≤ 50 000). Тут n - кількість вершин у графі. Вершини пронумеровані з 1 до n. Ребра задані множиною реберно-неперетинаючих шляхів, де m - число таких шляхів.
Кожен з наступних m рядків містить шлях у графі. Шлях починається числом k[i] (2 ≤ k[i] ≤ 1000), за яким слідують k[i] цілих чисел від 1 до n. Ці k[i] числа представляють вершини графа в шляху. Сусідні вершини в шляху різні. Шлях може проходити по одній вершині кілька разів, проте кожне ребро зустрічається лише один раз.
Граф у прикладі є кактусом.
Вихідні дані
Виведіть одне число - кількість варіантів перемістити ребро в кактусі.