Problem Description

On the slope of a mountain, there are some ski trails and one ski lift. All trails go from the top of the mountain to the bottom.

Every morning, a group of workers checks the condition of the trails. They take the lift together to the top. Then each worker skis down along a trail of their choice to the bottom, and each worker can ski down only once.

The trails chosen by different workers may overlap partly. Each trail can be checked by any worker who skis down. When skiing downhill, a worker chooses a route from high to low.

The ski trails form a network of open areas, and each area has a different height. Between any two areas, there is at most one path connecting them.

Input Format

The first line contains an integer $n$, the number of open areas.

In the next $n - 1$ lines, line $i + 1$ contains integers describing which areas have trails leading down to area $i$. The first integer is $k$, the number of such areas, followed by $k$ integers giving their indices (listed from west to east). In particular, the top of the mountain is numbered $1$, and the bottom is numbered $n$.

Output Format

Output one line with the minimum number of workers needed to check all ski trails.

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

Hint

Constraints: $2 \le n \le 5000$. The given graph is a planar graph.

Translated by ChatGPT 5