33OJ
登录 注册

#CF1887B. 时间旅行 / Time Travel

时间旅行 / Time Travel

题目描述

Berland 是一个历史悠久的国家,数百年来道路不断修建与损毁。Berland 的城市数量始终为 nn 座。你拥有这个国家历史上 tt 个关键时间点的记录,编号从 11 到 tt。每条记录保存该时刻部分城市之间的无向道路,代表在这个时刻可以通行的道路。

你得到一台时光机,它会把你在各个关键时间点之间传送。你无法自主选择抵达的时刻,但你知道时光机传送的时间序列 aia_i。两次传送间隔很短:当你被传送到下一个关键时间点之后(包含最后一次传送完成之后),你最多可以走该时刻存在的一条道路,并且必须从传送前所在的城市出发。

你的初始位置在城市 11,时光机已经将你传送到时刻 a1a_1。你希望尽快抵达城市 nn。求最少需要多少次传送(第一次传送也要计入)才能到达城市 nn。

输入格式

第一行两个整数 n,tn,t(2≤n≤2⋅105, 1≤t≤2⋅1052 \le n \le 2\cdot 10^5,\ 1 \le t \le 2\cdot 10^5)——城市数量、历史关键时间点记录数量。接下来依次给出 tt 条记录。

每条记录第一行一个整数 mim_i($0 \le m_i \le \min\left(\dfrac{n(n-1)}{2},2\cdot 10^5\right)$)——第 ii 条记录中的道路条数。

之后 mim_i 行,每行两个整数 vj,ujv_j,u_j(1≤vj,uj≤n, vj≠uj1\le v_j,u_j\le n,\ v_j\neq u_j),代表该时刻第 jj 条道路连接的两座城市。

下一行一个整数 kk(1≤k≤2⋅1051\le k\le 2\cdot 10^5)——时光机总共的传送次数。

再下一行 kk 个整数 a1,a2,…,aka_1,a_2,\dots,a_k(1≤ai≤t1\le a_i\le t),代表每次传送之后所处的时间点。

保证全部记录的 mim_i 之和不超过 2⋅1052\cdot 10^5;同一条记录内不会重复出现无序对 (u,v)(u,v)。

输出格式

输出一个整数:从城市 11 到达城市 nn 需要的最少传送次数;无法到达输出 −1-1。

注意:传送到时刻 a1a_1 同样算作一次传送。

5 2
4
1 2
2 3
3 4
4 5
2
2 3
3 5
6
2 1 2 1 2 1
5
5 2
3
1 2
3 1
4 3
2
2 1
4 5
5
1 2 1 1 1
-1

说明

第一个样例:初始位于城市 11,传送到时刻 a1=2a_1=2。没有可以走的道路,什么都不做,继续传送到 a2=1a_2=1,沿着道路 (1,2)(1,2) 移动。传送到 a3=2a_3=2,沿道路 (2,3)(2,3) 移动。传送到 a4=1a_4=1,停留在城市 33。传送到 a5=2a_5=2,沿道路 (3,5)(3,5) 抵达目标城市,一共 55 次传送。

第二个样例:在给定传送序列下无法到达城市 55。

原题链接

原题链接