#CF1887B. 时间旅行 / Time Travel
时间旅行 / Time Travel
题目描述
Berland 是一个历史悠久的国家,数百年来道路不断修建与损毁。Berland 的城市数量始终为 座。你拥有这个国家历史上 个关键时间点的记录,编号从 到 。每条记录保存该时刻部分城市之间的无向道路,代表在这个时刻可以通行的道路。
你得到一台时光机,它会把你在各个关键时间点之间传送。你无法自主选择抵达的时刻,但你知道时光机传送的时间序列 。两次传送间隔很短:当你被传送到下一个关键时间点之后(包含最后一次传送完成之后),你最多可以走该时刻存在的一条道路,并且必须从传送前所在的城市出发。
你的初始位置在城市 ,时光机已经将你传送到时刻 。你希望尽快抵达城市 。求最少需要多少次传送(第一次传送也要计入)才能到达城市 。
输入格式
第一行两个整数 ()——城市数量、历史关键时间点记录数量。接下来依次给出 条记录。
每条记录第一行一个整数 ($0 \le m_i \le \min\left(\dfrac{n(n-1)}{2},2\cdot 10^5\right)$)——第 条记录中的道路条数。
之后 行,每行两个整数 (),代表该时刻第 条道路连接的两座城市。
下一行一个整数 ()——时光机总共的传送次数。
再下一行 个整数 (),代表每次传送之后所处的时间点。
保证全部记录的 之和不超过 ;同一条记录内不会重复出现无序对 。
输出格式
输出一个整数:从城市 到达城市 需要的最少传送次数;无法到达输出 。
注意:传送到时刻 同样算作一次传送。
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
说明
第一个样例:初始位于城市 ,传送到时刻 。没有可以走的道路,什么都不做,继续传送到 ,沿着道路 移动。传送到 ,沿道路 移动。传送到 ,停留在城市 。传送到 ,沿道路 抵达目标城市,一共 次传送。
第二个样例:在给定传送序列下无法到达城市 。