A4. Travel / 旅行

题目描述

Yan 很喜欢开车在 Iatiland 全国各地旅行。

Iatiland 一共有 N 个城市，编号为 1 到 N。城市之间有若干条双向直接道路。对于每个城市，给出了一个按顺序排列的相邻城市列表，表示从该城市可以通过一条直接道路到达哪些城市。

保证任意两座城市之间都存在且仅存在一条简单路径。这意味着整张图是一棵树，因此一共恰好有 N-1 条直接道路。

Yan 喜欢“有规律地”旅行，于是他设计了如下行程规则：

• 第 1 天，他在城市 1；
• 之后的每一天，他都会从当前所在城市沿着一条直接道路走到相邻城市；
• 在当前城市时，他总是选择该城市相邻列表中的第一条道路；
• 但为了避免过程太无聊，每次在决定下一步要走哪条路之后，他都会把这条道路从列表开头删除，并追加到列表末尾。

Yan 一共有 M 个朋友想要拜访，编号为 1 到 M，其中第 i 个朋友住在城市 P_i。

只有当 Yan 当前正好在城市 P_i 时，才能拜访第 i 个朋友；并且他必须按照给定顺序拜访，也就是说，在拜访朋友 i 之前，不能先拜访朋友 i+1。

请你帮助 Yan 求出：最少经过多少天，他才能按顺序拜访完所有朋友。

输入格式

• 第 1 行：两个整数 N, M。
• 接下来 N 行：第 i 行先给出整数 k_i，表示城市 i 的直接相邻城市个数；随后给出 k_i 个整数，表示城市 i 的初始相邻城市列表。
• 最后一行：M 个整数 P_1, P_2, ..., P_M，表示各个朋友所在的城市。

输出格式

输出一个整数，表示所求的最小天数。

约束条件

• 1 <= N <= 5 * 10^5
• 1 <= M <= 5 * 10^5
• 1 <= k_i <= N - 1
• 1 <= P_i <= N

子任务

只有当某个子任务中的所有测试点全部通过时，才能获得该子任务的分数。

样例

输入

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

输出

9

说明

Yan 在前 9 天依次经过的城市为：

1, 2, 1, 3, 1, 2, 1, 3, 4

因此：

• 第 2 天拜访朋友 1；
• 第 3 天拜访朋友 2；
• 第 5 天拜访朋友 3；
• 第 9 天拜访朋友 4。