Minimum Race Starting Times

In this problem, you are given p participants and r races. Each race requires a set of participants, and a race can only be held at a certain starting time. Two races conflict if they share at least one participant, which means they cannot be scheduled at the same starting time. To avoid any scheduling conflicts, you must determine the minimum number of distinct starting times required.

The answer depends on the structure of the conflict graph constructed from the races. In particular, if the conflict graph is bipartite, then only two starting times are needed. Otherwise, at least three starting times are required.

More formally, let \(G=(V,E)\) be a graph where each vertex in \(V\) represents a race, and an edge exists between any two races if they share a participant. If \(G\) is bipartite (i.e., it can be colored with two colors such that no two adjacent vertices share the same color), the answer is 2; otherwise, the answer is 3.

inputFormat

The input is read from standard input (stdin) and has the following format:

p r
k1 a1,1 a1,2 ... a1,k₁
k2 a2,1 a2,2 ... a2,k₂
...
kr ar,1 ar,2 ... ar,kᵣ

Here, the first line contains two integers: p (the number of participants) and r (the number of races). Each of the next r lines describes a race. For each race, the first integer k denotes the number of participants in that race, followed by k integers representing the participant identifiers.

outputFormat

Output a single integer to standard output (stdout) representing the minimum number of distinct starting times required to schedule all races such that no participant is required to be in two races at the same time.

3 4
2 1 2
2 3 1
1 3
3 1 2 3

3