Minimum Distinct Station Levels on a Railway

On a one‐way railway there are (n) train stations numbered (1,2,\dots,n). Each station is assigned a level, with the minimum level being (1). Several train trips operate along this line. Each trip obeys the following rule: if a trip stops at station (x), then among all stations between its starting station and its terminal station (which are always stops), every station with a level greater than or equal to the level of station (x) must also be stopped at. In other words, for any trip with interval ([l, r]) and stop set (S) (where (l = \min S) and (r=\max S)), for every station (i) with (l \le i \le r) that is not in (S) we must have: [ f(i) < \min_{j\in S} f(j). ]

Given the running records for (m) trips (each of which satisfies the condition above), determine the minimum number of distinct levels that the (n) stations must have. (You are free to assign levels (positive integers) to stations subject to all the constraints, and you wish to minimize the number of distinct values used.)

All formulas are given in (\LaTeX) format and the problem description may include HTML formatting.

inputFormat

The first line contains two integers (n) and (m) ((1 \le n, m \le \text{reasonable limits})), representing the number of stations and the number of trips respectively. Then (m) trip records follow. Each trip record starts with an integer (k) ((k \ge 2)), indicating the number of stops for that trip. This is followed by (k) distinct integers in strictly increasing order representing the station numbers at which the trip stops. Note that the first and last stations in each record are the starting station and terminal station respectively.

outputFormat

Output a single integer, the minimum number of distinct levels that the (n) stations can be assigned, such that all trips satisfy the condition.

sample

5 1
3 1 3 5

2