Diameter of a Cactus

Time limit1sMemory limit128 MB

Summary
Given a cactus graph (each edge in at most one cycle), compute the maximum shortest-path distance between any two vertices.
Level

Hard9 of 10

Topics
Graph, DFS, Tree, Dynamic programming
Solved
No attempts yet

Problem

A cactus graph is a connected undirected graph in which every edge belongs to at most one simple cycle. You can think of it as paths and cycles attached to one another in a tree-like structure.

The diameter of a graph is the maximum, over all pairs of vertices, of the shortest-path distance between the two vertices. Given a cactus graph, find its diameter.

Input

The first line contains the number of vertices N (1 <= N <= 50,000) and the number of edge sets M (0 <= M <= 10,000).

Each of the next M lines describes one edge set. The first integer K_i (1 <= K_i <= 1,000) is the number of vertex numbers in that line. It is followed by K_i vertex numbers v_1, v_2, ..., v_{K_i}. For every adjacent pair in this list, the edge between those two vertices is included in the graph.

The graph described by the input is a cactus graph.

Output

Print the diameter of the cactus graph.

Examples1

  1. Example 1

    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
    8