#731. 车站分级

车站分级

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

一条单向的铁路线上,依次有编号为 1,2,...,n\red{1, 2, ..., n}n\red{n} 个火车站。每个火车站都有一个级别,最低为 1\red{1} 级。现有若干趟车次在这条线路上行驶,每一趟都满足如下要求:如果这趟车次停靠了火车站x\red{x},则始发站、终点站之间所有级别大于等于火车站 x\red{x} 的都必须停靠。 (注意:起始站和终点站自然也算作事先已知需要停靠的站点) 例如,下表是 5\red{5} 趟车次的运行情况。其中,前 4\red{4} 趟车次均满足要求,而第5\red{ 5} 趟车次由于停靠了 3\red{3 }号火车站(2\red2 级)却未停靠途经的 6\red{6} 号火车站(亦为2\red{ 2} 级)而不满足要求。

img

现有 m\red{m} 趟车次的运行情况(全部满足要求),试推算这 n\red{n }个火车站至少分为几个不同的级别。

输入格式

第一行包含 2\red{2} 个正整数 n,m\red{n, m},用一个空格隔开。 第 i+1\red{i + 1}(1im)\red{(1 ≤ i ≤ m)}中,首先是一个正整数si(2sin)\red{ s_i (2 ≤ s_i ≤ n)},表示第i\red{ i} 趟车次有 si\red{s_i }个停靠站;接下来有si\red{ s_i }个正整数,表示所有停靠站的编号,从小到大排列。每两个数之间用一个空格隔开。输入保证所有的车次都满足要求。

输出格式

输出只有一行,包含一个正整数,即n\red{ n }个火车站最少划分的级别数。

样例

样例输入

9 2
4 1 3 5 6
3 3 5 6

样例输出

2

数据范围与提示

对于 20%\red{20\%}的数据,1n,m10\red{1 ≤ n, m ≤ 10}; 对于50%\red{ 50\%}的数据,1n,m100\red{1 ≤ n, m ≤ 100}; 对于 100%\red{100\%}的数据,1n,m1000\red{1 ≤ n, m ≤ 1000}

中心团队A班 图的复习2

未参加
状态
已结束
规则
IOI
题目
4
开始于
2024-3-23 15:30
结束于
2024-3-30 7:30
持续时间
160 小时
主持人
参赛人数
26