Problem Description

A grand academic conference is held in Bajtocja and lasts for $k$ days. Each day, several talks are held simultaneously (at the same time). Also, some talks are continuations of talks from the previous day.

Each participant can attend at most one talk per day. Moreover, if talk $b$ is a continuation of talk $a$, then a participant can attend talk $b$ only if they attended talk $a$ the day before. A talk can be a continuation of at most one talk from the previous day, but multiple talks may be continuations of the same talk (their participants split into several groups on the next day, and some people may not attend any continuation talk).

The King of Bajtocja wants to know exactly what happens at every talk, so he decides to send his trusted staff to attend the talks. Help him determine the minimum number of staff members that must be sent so that every talk has at least one staff member attending.

Input Format

The first line of input contains two positive integers $k$ and $n_1$ ($1 \le k, n_1 \le 500\,000$), representing the number of days of the conference and the number of talks held on the first day (since it is the first day, no talk can be a continuation of an earlier talk).

Next, if $k > 1$, then for $2 \le i \le k$, line $i$ contains the description of day $i$. The line starts with a positive integer $n_i$ ($1 \le n_i \le 500\,000$), the number of talks held on day $i$, followed by $n_i$ integers $a_{i,1}, \dots, a_{i,n_i}$ ($0 \le a_{i,j} \le n_{i-1}$). $a_{i,j} = 0$ means that the $j$-th talk on day $i$ is not a continuation of any earlier talk; if $a_{i,j} > 0$, then the $j$-th talk on day $i$ is a continuation of the $a_{i,j}$-th talk on day $i-1$.

The talks on each day are numbered from $1$ to $n_i$. The total number of talks, i.e., the sum of all $n_i$, does not exceed $500\,000$.

Output Format

Output one line containing one integer, the answer.

4 3
3 1 1 1
4 0 0 2 0
2 3 3

6

Hint

Explanation of the sample: We send six staff members to the talks, call them A, B, C, D, E, and F. On the first day, send A, B, C, and D to attend the first talk, E to attend the second talk, and F to attend the third talk.

On the second day, E and F stay at home (there is no talk they can attend), A and B attend the second talk, and C and D attend the first and the third talks, respectively.

On the third day, A and B attend the third talk; for each of the other talks, we send one of the remaining staff members.

On the last day, A and B attend the first and the second talks, respectively.

It can be verified that five staff members cannot cover all talks.

Translated by ChatGPT 5