Problem Background

NOIP2013 Junior Group T4

Problem Description

On a single-directional railway line, there are \( n \) train stations numbered \( 1, 2, \ldots, n \). Each station has a level, with the minimum being level \( 1 \). There are several train services operating on this line, each fulfilling the following requirement: if a train service stops at station \( x \), then all stations between the starting and ending stations with levels greater than or equal to station \( x \) must also be停靠.
Note: The starting and ending stations are naturally considered as known stops.

For example, the table below shows the operation of 5 train services. The first 4 services meet the requirements, while the 5th service does not, as it stops at station 3 (level 2) but does not stop at station 6 (also level 2).

Given the operation details of \( m \) train services (all meeting the requirements), calculate the minimum number of different levels into which the \( n \) train stations can be classified.

Input Format

The first line contains two positive integers \( n \) and \( m \), separated by a space.

The \( i + 1 \)-th line (\( 1 \leq i \leq m \)) begins with a positive integer \( s_i \) (\( 2 \leq s_i \leq n \)), indicating that the \( i \)-th train service has \( s_i \) stops; followed by \( s_i \) positive integers representing the stop numbers, sorted in ascending order, with each two numbers separated by a space. The input ensures that all train services meet the requirements.

Output Format

A single positive integer, the minimum number of levels into which the \( n \) train stations can be classified.

Sample Input and Output

Input Sample #1

9 2 
4 1 3 5 6 
3 3 5 6 

Output Sample #1

2

Input Sample #2

9 3 
4 1 3 5 6 
3 3 5 6 
3 1 5 9 

Output Sample #2

3

Notes

For 20% of the data, \( 1 \leq n, m \leq 10 \);

For 50% of the data, \( 1 \leq n, m \leq 100 \);

For 100% of the data, \( 1 \leq n, m \leq 1000 \).

见题面 Input 部分

见题面 Output 部分