Problem Description

This problem is translated from PA 2022 Round 5 Walizki.

Have you ever wondered where your suitcase goes after you check in at the airport? Behind the curtain where they disappear, there is a huge hall full of complicated platforms and conveyor belts that sort your luggage.

Byteasar is responsible for evaluating the design of the luggage hall of the newly planned Byteburg Bitom Airport. According to the plan, there will be $n$ platforms in the hall, numbered from $1$ to $n$. Each suitcase is initially sent to platform $1$. Some one-way conveyor belts can leave a platform and connect to platforms with strictly larger indices. If a platform has no outgoing conveyor belts, then suitcases at this platform are manually taken away by airport staff and moved to the corresponding plane. On the other hand, if a platform has multiple outgoing conveyor belts, then their order matters: the first suitcase that reaches such a platform leaves via the first belt, the second leaves via the second belt, and so on. After a suitcase leaves via the last belt, the next suitcase again leaves via the first belt, repeating in a cycle.

Once a suitcase is placed onto platform $1$, its transportation on the belts and its collection by staff are completed before the next suitcase is placed onto platform $1$. In other words, at any time, there is at most one suitcase being transported on the conveyor belts.

It is easy to see that after processing some number of suitcases, this luggage system will “reset”, meaning that for every platform with outgoing belts, the next suitcase arriving at that platform will leave via the first outgoing belt again. Byteasar wants to know the minimum number of suitcases that need to be processed before the system resets by itself. Please compute this value.

Input Format

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

The next $n$ lines describe the platforms. The $i$-th line starts with a non-negative integer $r_i$, the number of conveyor belts leaving platform $i$. If $r_i=0$, it means that staff take the suitcase from this platform. If $r_i>0$, the line then contains $r_i$ integers $l_{i,1}, l_{i,2}, \ldots, l_{i,r_i}$, in order, representing the platform indices that the outgoing belts lead to (the destination indices are also strictly increasing).

Output Format

Output one integer on one line, the minimum number of suitcases that must be processed before the system resets.

7
3 2 3 5
2 3 6
3 5 6 7
1 6
1 7
0
0

6

3
0
1 3
0

1

Hint

For $100\%$ of the testdata, it holds that:

$1\le n\le 100, i<l_{i,1}<l_{i,2}<\ldots<l_{i,r_i}$。

Translated by ChatGPT 5