Maximum Matching of a Cactus

Time limit0.3sMemory limit1024 MB

Summary

Given a cactus graph as a list of edge sets (cycles or paths), find the size of its maximum matching. Each edge set is a chain of vertices.

Level: Medium6 of 10
Topics: Tree, Dynamic programming, Graph
Solved: No attempts yet

Problem

In a graph, a matching is a subset of edges in which no two edges share an endpoint. The maximum matching is a matching with the largest number of edges.

An undirected simple connected graph is called a cactus graph if any two distinct simple cycles share at most one common vertex.

Compute the size of the maximum matching of a cactus graph.

Input

The first line contains the number of vertices $N$ ( $1 \\le N \\le 50{,}000$ ) and the number of edge sets $M$ ( $0 \\le M \\le 50{,}000$ ).

Each of the next $M$ lines describes one edge set. The first number $K_i$ ( $1 \\le K_i \\le 1{,}000$ ) on line $i$ is the number of vertices in the $i$ -th edge set. The next $K_i$ numbers are vertex numbers. Each pair of consecutive vertices in the list has an edge that belongs to the set.

Output

Print the size of the maximum matching of the cactus graph.

Examples5

Example 1
Input
```
4 2
3 1 2 3
2 2 4
```
Expected output
```
1
```

Example 2

Input

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

Expected output

Example 3
Input
```
2 1
2 1 2
```
Expected output
```
1
```

Example 4

Input

Expected output

Example 5
Input
```
6 1
7 1 2 5 6 2 3 4
```
Expected output
```
3
```