Это 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 чисел представляют вершины графа в пути. Соседние вершины в пути различны. Путь может проходить по одной вершине несколько раз, однако каждое ребро встречается только один раз.

Граф в примере является кактусом.

Выходные данные

Вывести одно число - количество вариантов передвинуть ребро в кактусе.