CF1887B.Time Travel

题意简述

给定一张 $ n $ 个点的无向完全图和 $ t $ 组边集，边集 $ i $ 的大小为 $ m_i $。每到达一个结点，你都必须至少等待 $ 1 $ 秒，才能继续前进。每条边的通过时间都是 $ 0 $ 秒。第 $ i $ 秒时，边集 $ a_i $ 中的边可以通行，其余边不能通行。第 $ 0 $ 秒时，你从结点 $ 1 $ 出发。判断是否可以在 $ k $ 秒内到达结点 $ n $。如果可以，求出从结点 $ 1 $ 到结点 $ n $ 的最少用时。

注：当你在结点 $ 1 $ 时，也必须至少等待 $ 1 $ 秒才能出发。

输入数据的第一行包含两个整数 $ n $ 和 $ t \left(2 \le n \le 2 \times 10^5, 1 \le t \le 2 \times 10^5\right) $，意义如上。

接下来的输入数据包含 $ t $ 个部分。

第 $ i $ 个部分的第一行包含一个整数 $ m_i \left(0 \le m_i \le \min \left(\frac{n(n-1)}{2}, 2 \times 10^5\right)\right) $，表示边集 $ i $ 的大小。

在每个部分接下来的 $ m_i $ 行中，每行包含两个整数 $ u_j $ 和 $ v_j \left(1 \le u_j, v_j \le n, u_j \neq v_j\right) $ 表示边集 $ i $ 的第 $ j $ 条边连接着结点 $ u_j $ 和 $ v_j $。

在上述 $ t $ 个部分结束后的一行包含一个整数 $ k $，意义如上。

接下来的一行包含 $ k $ 个整数 $ a_1, a_2, \dots, a_k \left(1 \le a_i \le t\right) $，意义如上。

输入数据保证 $ \sum m_i \le 2 \times 10^5 $，保证在同一个边集中没有重边，保证没有自环。

如果可以在 $ k $ 秒内从结点 $ 1 $ 到达结点 $ n $，输出最少用时，否则输出 -1。

样例解释

在第一个样例中，因为边集 $ a_1 = 2 $ 中没有边连接着结点 $ 1 $，所以你只能从第 $ 0 $ 秒等待至第 $ 2 $ 秒，然后在边集 $ a_2 = 1 $ 中选择从边 $ \left(1, 2\right) $ 移动至结点 $ 2 $。在结点 $ 2 $ 时，你必须等待至第 $ 3 $ 秒，再选择边集 $ a_3 = 2 $ 中的边 $ \left(2, 3\right) $ 移动至结点 $ 3 $。在结点 $ 3 $ 时，你选择等待至第 $ 5 $ 秒，然后在边集 $ a_5 = 2 $ 中选择从边 $ \left(3, 5\right) $ 移动至结点 $ 5 $。可以证明 $ 5 $ 秒即为最短用时。

对于第二个样例，可以证明无法在 $ 5 $ 秒内到达结点 $ n $。