# DFS + Cycles + Cactus

# Cactus Jubilee

This is the **20**-th Northeastern European Regional Contest (NEERC). Cactus problems had become a
NEERC tradition. The first Cactus problem was given in 2005, so there is a jubilee - **10** years of Cactus.

Cactus is a connected undirected graph in which every edge lies on at most one simple cycle. Intuitively cactus is a generalization of a tree where some cycles are allowed. Multiedges (multiple edges between a pair of vertices) and loops (edges that connect a vertex to itself) are not allowed in a cactus.

You are given a cactus. Let’s move an edge - remove one of graph’s edges, but connect a different pair of vertices with an edge, so that a graph still remains a cactus. How many ways are there to perform such a move?

For example, in the left cactus above (given in the first sample), there are **42** ways to perform an edge move. In the right cactus (given in the second sample), which is the classical NEERC cactus since the original problem in **2005**, there are **216** ways to perform a move.

#### Input

The first line contains two integers **n** and **m** (**1** ≤ **n** ≤ **50 000**, **0** ≤ **m** ≤ **50 000**). Here **n** is the number of vertices in the graph. Vertices are numbered from **1** to **n**. Edges of the graph are represented by a set of edge-distinct paths, where **m** is the number of such paths.

Each of the following **m** lines contains a path in the graph. A path starts with an integer `k`

(_{i}**2** ≤ `k`

≤ _{i}**1000**) followed by `k`

integers from _{i}**1** to **n**. These `k`

integers represent vertices of a path. Adjacent vertices in a path are distinct. Path can go to the same vertex multiple times, but every edge is traversed exactly once in the whole input._{i}

The graph in the input is a cactus.

#### Output

Write a single integer - the number of ways to move an edge in the cactus.

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