Description

If, in an undirected connected graph, every edge appears in at most one simple cycle, we call the graph a cactus graph (cactus). A simple cycle is a cycle that does not visit any vertex more than once.

For example, the first figure above is a cactus graph, while the second is not—note that it has three simple cycles: (4, 3, 2, 1, 6, 5, 4), (7, 8, 9, 10, 2, 3, 7), and (4, 3, 7, 8, 9, 10, 2, 1, 6, 5, 4), and the edge (2, 3) appears in the first two simple cycles at the same time. In addition, the third figure is not a cactus graph either because it is not connected. Clearly, every edge in a cactus graph is either a bridge or lies in exactly one simple cycle; exactly one of these holds.

Define the distance between two vertices in the graph as the length of the shortest path between them. Define the diameter of a graph as the distance between the two vertices that are farthest apart. We assume every edge in the cactus graph has weight 1. Your task is to compute the diameter of the given cactus graph.

Input Format

The first line contains two integers $n$ and $m$ ($1 \le n \le 50000$, $0 \le m \le 10000$). Here $n$ is the number of vertices, labeled from 1 to $n$.

The next $m$ lines each describe one path. Each such line starts with an integer $k$ ($2 \le k \le 1000$), the number of vertices on this path, followed by $k$ integers between 1 and $n$, each denoting a vertex. Adjacent vertices on the line indicate an edge between them. A path may pass through a vertex multiple times; for example, in the first sample, the first path goes from 3 to 8, then returns from 8 to 3. We guarantee that every edge appears in some path, and no edge appears in two different paths or appears twice within the same path.

Output Format

Output a single integer: the diameter of the cactus graph.

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

8

10 1
10 1 2 3 4 5 6 7 8 9 10

9

Hint

Explanation for the first sample: the shortest path length between vertex 6 and vertex 12 is 8, so the diameter is 8.

Note for Pascal users: your program may encounter stack overflow on large testdata. If you need to adjust the stack size, you can add the following at the beginning of your program: {$M 5000000}, where 5000000 specifies the stack size. Please choose an appropriate value for your program.

Translated by ChatGPT 5