1 人解决，1 人已尝试。
1 份提交通过，共有 1 份提交。
8.9 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 MB
A ski team organizes a training on the Bytemountain. There is one ski lift on the northern slope of the mountain. All the ski runs lead from the upper ski lift station to the bottom one. During the training the team members will start together from the upper station and meet at the bottom one. Apart from these two points, the ski runs of the competitors cannot intersect, nor adhere to each other. All ski runs always have to lead downwards.
A map of ski runs consists of net of clearings connected by glades. Every clearing lies on a different height. Two clearings can be joint directly with at most one glade. While skiing downhill from the upper to the bottom station of ski lift, one can choose way to visit any clearing (but maybe not all in one downhill run). Ski runs can intersect only on the clearings and do not lead through tunnels, or flyovers.
Task
Write a program, which:
1.reads the map of ski runs,
2.determines maximum number of competitors who can participate in training,
3.write the result.
In the first line of the input , there is an integer n, that equals to the number of the clearings, 2 <= n <= 5 000.
In each of the next n-1 lines there is a sequence of integers separated by single spaces. Numbers in the (i+1)-th line describe, to which clearings the downhill glades from the i-th clearing lead. First integer in the line - k is the number of these clearings, and the following k integers are their numbers, which are ordered according to the arrangement of glades leading to them, in east to west direction. The clearings are numbered from 1 to n. The upper station of the ski lift can be found on the clearing number 1 and the bottom one on the clearing number n.
The first and the only one line of the output should consist of exactly one integer - the maximum number of skiers able to take part in the training.
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
3
1 人解决，1 人已尝试。
1 份提交通过，共有 1 份提交。
8.9 EMB 奖励。