1101. Speleology

单点时限: 2.0 sec

内存限制: 256 MB

A team of speleologists organizes a training in the Grate Cave of Byte Mountains. During the training each speleologist explores a route from Top Chamber to Bottom Chamber. The speleologists may move down only, i.e. the level of every consecutive chamber on a route should be lower then the previous one. Moreover, each speleologist has to start from Top Chamber through a different corridor and each of them must enter Bottom Chamber using different corridor. The remaining corridors may be traversed by more then one speleologist. How many speleologists can train simultaneously?

Task

Write a program which:

reads the cave description,

computes the maximal number of speleologists that may train simultaneously,

writes the result.

输入格式

In the first line there is one integer n (2<=n<=200), equal to the number of chambers in the cave. The chambers are numbered with integers from 1 to n in descending level order - the chamber of grater number is at the higher level than the chamber of the lower one. (Top Chamber has number 1, and Bottom Chamber has number n). In the following n-1lines (i.e. lines 2,3,…,n) the descriptions of corridors are given. The (i+1)-th line contains numbers of chambers connected by corridors with the i-th chamber. (only chambers with numbers grater then i are mentioned). The first number in a line, m, 0<=m<=(n-i+1), is a number of corridors exiting the chamber being described. Then the following m integers are the numbers of the chambers the corridors are leading to.

输出格式

Your program should write one integer in the only line. This number should be equal to the maximal number of speleologists able to train simultaneously,

样例

Input
12
4 3 4 2 5
1 8
2 9 7
2 6 11
1 8
2 9 10
2 10 11
1 12
2 10 12
1 12
1 12
describing the following cave:
Output
3

6 人解决,7 人已尝试。

6 份提交通过,共有 24 份提交。

6.7 EMB 奖励。

创建: 16 年,10 月前.

修改: 6 年,9 月前.

最后提交: 3 年,6 月前.

来源: POI 1999 II Stage

题目标签