P16390 [IATI 2024] Travel

Yan 喜欢开着他的车在 Iatiland 旅行。 由于 Yan 旅行了很长时间，他已经想出了对整个国家地图的描述。Iatiland 的城市编号从 $1$ 到 $N$，城市之间有双向的直接道路连接不同的城市。对于每个城市，他有一个从该城市通过一条直接道路可以到达的城市列表。数据保证，任意两个城市之间都存在唯一的路径。注意，该路径可能不是直接的，即可能会经过多条直接道路。注意到这意味着直接道路的总数为 $N - 1$ 条。 Yan 喜欢系统地旅行，因此他想出了一个在周游全国时将遵循的算法。 他在第 $1$ 天从城市 $1$ 开始他的旅程，之后的每一天他都会从他当前所在的城市沿一条直接道路出发。他选择的道路总是当前城市列表中的第一条道路。然而，这个简单的过程对 Yan 来说显得相当无聊，所以在选好下一次将走的道路之后，他会将其从列表的开头移除，并将其追加到列表末尾。 Yan 旅行的主要目的是拜访他的朋友们并和他们闲聊。他有 $M$ 个想要拜访的朋友，编号从 $1$ 到 $M$，每个朋友 $i$ 住在城市 $P_i$。只有当 Yan 当前正处于城市 $P_i$ 时，他才能拜访朋友 $i$。此外，Yan 想要按照给定的顺序拜访他的朋友们，即他不能在拜访朋友 $i$ 之前先拜访朋友 $i+1$。 请帮助 Yan 求出他按正确顺序拜访完所有朋友所需的最少天数。

标准输入的第一行包含 $2$ 个整数 —— $N$ 和 $M$。 接下来是 $N$ 行，在第 $i$ 行中，首先给出 $k_i$ —— 从城市 $i$ 出发的直接道路条数，然后给出 $k_i$ 个整数 —— 与城市 $i$ 以直接道路相连的城市的初始列表。 接下来一行包含 $M$ 个整数 —— $P_i$，即 Yan 的朋友们居住的城市编号。

在标准输出上的一行中输出所需的最少天数。

### 样例解释 Yan 的旅程将花费 $9$ 天，依次经过城市 $1,\textbf{2},\textbf{1},3,\textbf{1},2,1,3,\textbf{4}$。他将在第 $2$ 天见到朋友 $1$，第 $3$ 天见到朋友 $2$，第 $5$ 天见到朋友 $3$，第 $9$ 天见到朋友 $4$。 ### 数据范围 - $1 \leq N \leq 5\times 10^5$ - $1 \leq M \leq 5\times 10^5$ - $1 \leq k_i \leq N - 1$ - $1 \leq P_i \leq N$ ### 子任务 | **子任务** | **分数** | **$N$** | **$M$** | **附加约束** | | :---: | :---: | :---: | :---: | :---: | | $1$ | $10$ | $\leq 50$ | $\leq 50$ | 无 | | $2$ | $10$ | $\leq 1000$ | $\leq 1000$ | 无 | | $3$ | $20$ | $\leq 10^5$ | $\leq 1000$ | 无 | | $4$ | $10$ | $\leq 1000$ | $\leq 10^5$ | 无 | | $5$ | $15$ | $\leq 5\times10^5$ | $\leq 5\times10^5$ | $P_i = 1$ | | $6$ | $20$ | $\leq 10^5$ | $\leq 10^5$ | 无 | | $7$ | $15$ | $\leq 5\times10^5$ | $\leq 5\times10^5$ | 无 | 只有在成功通过某个子任务中指定的所有测试数据时，该子任务的分数才会被给出。 翻译由 DeepSeek V4 Pro 完成