[AdditionalFile5676.zip](file://AdditionalFile5676.zip?type=additional_file)

#5676. 「PA 2026」Konferencja

标签: 传统 | 时间限制: 1000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 PA 2026 Runda 1 Konferencja

在 Bajtocja 正在举办一场为期 $k$ 天的大型科学会议。每天都有一定数量的会议同时进行。此外，一些会议是前一天会议的延续。

每位参与者每天最多只能参加一场会议。此外，如果会议 $b$ 是会议 $a$ 的延续，那么参与者只有在前一天参加了会议 $a$，才能参加会议 $b$。一个会议最多只能是一个前一天会议的延续，但多个会议可以同时是同一个会议的延续（其参与者在第二天会分散成不同的小组，其中一些人可能不会参加任何延续会议）。

Bajtocja 国王想确切知道每个会议的情况，因此决定派他最信任的员工去参加会议。请帮助他确定最少需要派遣多少名员工，才能保证每个会议至少有一名员工参加。

输入格式

第一行包含两个正整数 $k$ 和 $n_{1}$ $(1 \leq k, n_{1} \leq 500000)$，分别表示会议的天数以及第一天举行的会议数量（由于是第一天，没有任何会议是之前会议的延续）。

随后，如果 $k > 1$，对于 $2 \leq i \leq k$，第 $i$ 行描述了第 $i$ 天的情况。该行首先是一个正整数 $n_{i}$ $(1 \leq n_{i} \leq 500000)$，表示第 $i$ 天举行的会议数量，随后是 $n_{i}$ 个整数 $a_{i, 1}, \ldots, a_{i, n_{i}}$ $(0 \leq a_{i, j} \leq n_{i-1})$。数值 $a_{i, j} = 0$ 表示第 $i$ 天的第 $j$ 个会议不是任何之前会议的延续；如果 $a_{i, j} > 0$，则表示第 $i$ 天的第 $j$ 个会议是第 $i-1$ 天第 $a_{i, j}$ 个会议的延续。

每一天的会议编号从 $1$ 到 $n_{i}$。会议总数（即所有 $n_{i}$ 的总和）不超过 $500000$。

输出格式

输出一个整数，表示最少需要派遣到会议上的员工数量，以确保每个会议至少有一名员工参加。

样例

输入

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

输出

6

我们派遣六名员工参加会议，记为 A, B, C, D, E 和 F。 第一天，派遣员工 A, B, C 和 D 参加第一个会议，派遣员工 E 参加第二个会议，派遣员工 F 参加第三个会议。

第二天，E 和 F 留在家中（没有他们可以参加的会议），员工 A 和 B 参加第二个会议，C 和 D 分别参加第一和第三个会议。

第三天，A 和 B 参加第三个会议；其余会议则派遣剩余员工中的各一人。

最后，在最后一天，A 和 B 参加第一和第二个会议。 可以看出，仅派遣五名员工是无法覆盖所有会议的。