OI题库

【题目描述】

在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