bzoj#P2979. [Poi2002]滑雪者

[Poi2002]滑雪者

//时间限制:1s 空间限制:128MB

题目描述

在某山的斜坡上有一些滑雪轨道和一个滑雪电梯,所有的轨道都是从山顶到山底。每天清晨一群滑雪工人检查轨道。他们一起乘电梯到山顶位置,接着他们沿每个人选择的轨道滑到底端。每个工人只能滑一次。工人的轨道可能有部分相同每个轨道可由任一个向下滑行的工人检查。滑雪轨道由一个被砍伐的空地网络组成。每个空地有不同的高度,任意两个空地的至多被一个砍伐的道路连接。向下滑雪从高到底选择一条轨道进行(尽管并不是他们中所有按单独运行)。滑雪轨道只在地带交叉,不会通过隧道和桥梁。

输入格式

第一行有一个整数 nn 表示空旷地的数目。空旷地编号从 11nn

下面连续的 n1n-1 行包一系列的整数。第 i+1i+1 行的整数表示空旷地 ii 有轨道滑向它们。 第一个整数 kk 表示空旷地数目,接着的 kk 个整数为它们的编号(按从西往东的方向排列),山顶编号为 11,山脚编号为 nn

输出格式

输出最少需要多少个工人检查所有的滑道。

样例输入

15
5 3 5 9 2 4
1 9
2 7 5
2 6 8
1 7
1 10
2 14 11
2 10 12
2 13 10
3 13 15 12
2 14 15
1 15
1 15
1 15

样例输出

8

数据规模与约定

对于 100%100\% 的数据,2n5×1032\leq n\leq 5 \times 10^3