Cactus Jubilee#7563
This is the -th Northeastern European Regional Contest (NEERC). Cactus problems had become aNEERC tradition. The first Cactus problem was given in , so there is a jubilee - years of Cactus.
Cactus is a connected undirected graph in which every edge lies on at most one simple cycle. Intuitivelycactus is a generalization of a tree where some cycles are allowed. Multiedges (multiple edges between apair 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 pairof vertices with an edge, so that a graph still remains a cactus. How many ways are there to performsuch a move?
For example, in the left cactus above (given in the first sample), there are 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 , there are ways to perform a move.
The first line contains two integers and (1 \leq n \leq 50000, 0 \leq m \leq 50000). Here is the number of vertices in the graph. Vertices are numbered from to . Edges of the graph are represented by a set of edge-distinct paths, where is the number of such paths.
Each of the following lines contains a path in the graph. A path starts with an integer k_i (2 \leq k_i \leq 1000) followed by k_i integers from to . These k_i 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.
The graph in the input is a cactus.
Write a single integer - the number of ways to move an edge in the cactus.
Esempio 1
Esempio 2