Cactus Graph

Time limit2sMemory limit128 MB

Summary

Given a graph described by edge-paths, verify it is a cactus and count connected spanning subgraphs that remain cactus graphs.

Level: Medium6 of 10
Topics: Graph, DFS, Combinatorics
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples3

Example 1

Input

14 3
9 1 2 3 4 5 6 7 8 3
7 2 9 10 11 12 13 10
2 2 14

Expected output

Example 2
Input
```
10 2
7 1 2 3 4 5 6 1
6 3 7 8 9 10 2
```
Expected output
```
0
```
Example 3
Input
```
5 1
4 1 2 3 4
```
Expected output
```
0
```