Cactus Graph

A tree is a connected undirected graph in which no edge belongs to any cycle. Similarly, a cactus graph is a connected undirected graph in which every edge belongs to at most one cycle.

A spanning subgraph contains every vertex of the original graph and uses some of the original edges, while remaining connected. The original graph itself is also counted as a spanning subgraph.

Given a graph, determine whether it is a cactus graph. If it is, compute the number of spanning subgraphs that are also cactus graphs.

The first line contains two integers N and M. N is the number of vertices in the graph, and M is the number of paths used to describe the edges.

• 1 <= N <= 20,000
• 0 <= M <= 1,000

Each of the next M lines describes one path. The first integer on the line is the number of vertices in that path, followed by the vertices of the path in order. Every pair of consecutive vertices on the same line forms an edge.

A vertex may appear in several paths, but each edge appears exactly once in the entire input. The given graph always has at most 2N edges.

If the graph is not a cactus graph, print 0 on the first line.

Otherwise, print the number of spanning subgraphs that are also cactus graphs on the first line.