CF555A Case of Matryoshkas

Android 侦探 Andrewid 是一位银河闻名的侦探。他正在调查当代艺术展上的一起恶意破坏事件。 展览的主要展品是一组由 $n$ 个俄罗斯套娃组成的结构，这些套娃可以依次嵌套在一起。套娃编号从 $1$ 到 $n$。编号较小的套娃可以嵌入编号较大的套娃中，两个套娃不能直接嵌入在同一个套娃里，但可以通过链式嵌套，例如 $1→2→4→5$。 你每秒可以进行以下两种操作之一： - 拥有一个未被任何套娃嵌套的套娃 $a$ 和一个未包含任何套娃且也未被嵌套的套娃 $b$ 时，可以将 $a$ 嵌入 $b$； - 拥有一个被套娃 $b$ 直接嵌套的套娃 $a$，并且 $b$ 未被其他套娃嵌套时，可以将 $a$ 从 $b$ 中取出； 根据现代美学规范，参展套娃原本被组装为若干个独立的链式结构，但犯罪分子按照神秘计划，将所有套娃全部拆开，并组装成了一个大链（$1→2→...→n$）。为了继续调查，Andrewid 需要知道，最少需要多少秒才能完成这个操作。

第一行包含两个整数 $n$（$1 \leq n \leq 10^{5}$）和 $k$（$1 \leq k \leq 10^{5}$），分别表示套娃数量和最初的套娃链数。 接下来的 $k$ 行描述了这些链式结构：第 $i$ 行首先包含数字 $m_i$（$1 \leq m_i \leq n$），接着是 $m_i$ 个数字 $a_{i1}, a_{i2}, \ldots, a_{im_i}$，表示第 $i$ 条链中各个套娃的编号（套娃 $a_{i1}$ 嵌入 $a_{i2}$，$a_{i2}$ 嵌入 $a_{i3}$，依此类推，直到 $a_{im_i}$，它未被嵌套在其他套娃中）。 保证 $m_1 + m_2 + \ldots + m_k = n$，且所有链中的套娃编号互不相同，每条链的套娃编号是递增排列的。

输出一个整数，表示把所有套娃组装成一个大链所需的最短时间（秒数）。

在第一个样例测试中，有两条链：$1→2$ 和 $3$。只需将第一条链嵌入到第二条链中，用 1 秒即可得到 $1→2→3$。 在第二个样例测试中，需要先将三条链全部拆成单个套娃（分别用 2 + 1 + 1 = 4 秒），然后再组装成一个大链共需 6 秒。 由 ChatGPT 5 翻译