Юбилей кактуса
Юбилей кактуса
Это 20-ое соревнование Северо-Восточного Европейского региона (NEERC). Задачи на кактусы стали традицией NEERC. Первая задача про кактусы была в 2005, поэтому сегодня юбилей - 10-летие кактуса.
Кактус - это связный неориентированный граф, в котором каждое ребро лежит не более чем на одном цикле. Интуитивно кактус - это обобщение дерева, в котором разрешены некоторые циклы. Мультиребра (несколько ребер между парой вершин) и петли (ребра соединяющие вершину с самой собой) в кактусе не разрешены.
Вам задан кактус. Давайте переместим ребро - удалим из графа одно ребро и соединим ребром другую пару вершин так чтобы граф остался кактусом. Сколько существует вариантов таких перемещений ребер?
Например в левом кактусе сверху (заданного в первом примере) существует 42 варианта перемещения ребра. В правом кактусе (задан во втором примере), который является стандартным примером кактуса еще с NEERC 2005 года, существует в точности 216 вариантов передвижения ребра.
Входные данные
Первая строка содержит два целых числа n и m (1 ≤ n ≤ 50 000, 0 ≤ m ≤ 50 000). Здесь n количество вершин в графе. Вершины пронумерованы с 1 до n. Ребра заданы множеством реберно - непересекающихся путей, где m число таких путей.
Каждая из следующих m строк содержит путь в графе. Путь начинается числом ki
(2 ≤ ki
≤ 1000), за которым следуют ki
целых чисел от 1 до n. Эти ki
чисел представляют вершины графа в пути. Соседние вершины в пути различны. Путь может проходить по одной вершине несколько раз, однако каждое ребро встречается только один раз.
Граф в примере является кактусом.
Выходные данные
Вывести одно число - количество вариантов передвинуть ребро в кактусе.
6 1 7 1 2 5 6 2 3 4
42
15 3 9 1 2 3 4 5 6 7 8 3 7 2 9 10 11 12 13 10 5 2 14 9 15 10
216