[POI2002]滑雪者

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file skiers.in Output file skiers.out

【题目描述】

在Byte山的南坡有一些滑雪道和滑雪缆车。它们都从山顶通向山底。每天早上工人们都会检查雪道的状况。他们一同坐缆车到山顶,然后分别按照一条选择好的线路滑到山底。每一位工人只滑一次。不同工人的滑雪线路可以部分重合。每一位工人都总是从上向下滑。

雪道的地图是一张由林中空地和连接它们的路径组成的网络。每片空地都有不同的高度。两篇空地可以被至多一条路径直接连接。一位从山顶出发的滑雪者可以选择一条路径来访问任意一片空地(尽管可能需要滑超过一次)。路径只会在空地处相交,也没有隧道或桥梁。

【输入格式】

输入文件的第一行是一个整数n,代表空地数量,2<=n<=5000。空地被编号为1~n。

接下来的n-1行包含一系列被空格分隔的整数。第(i+1)行包含所有从i号空地出发的路径所到达的空地。第一个整数k是这些空地的数量,接下来的k个整数按照从西到东的顺序给出了这些空地的编号。

山顶的空地编号为1,山底的空地编号为n。

【输出格式】

输出一行一个整数,即检查所有的雪道需要的最少工人数。

【样例输入】


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

【提示】

样例如图:

【来源】

POI 2002 Skiers