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 $。

In the first example, you are in city $ 1 $ and move to moment $ a_{1} = 2 $ . Since there are no suitable roads to pass, you do nothing and move to moment $ a_{2} = 1 $ , after which you travel along the road $ (1, 2) $ . Moving to moment $ a_{3} = 2 $ , you travel along the road $ (2, 3) $ . Moving to moment $ a_{4} = 1 $ , you stay in city $ 3 $ and make the next time travel. At time moment $ a_{5} = 2 $ , you travel along the road $ (3, 5) $ and end up in the final city after $ 5 $ time travels. In the second example, it can be shown that it is impossible to reach city $ 5 $ with the given time travels.