← 返回题目列表

Codeforces · 1887/B

B. 时间旅行

中文机器翻译题面 查看原题

Berland是一个有着古老历史的国家,几个世纪以来,这里的道路被修建和毁坏。众所周知,贝尔兰总是有 $$$n$$$ 城市。您还拥有该国历史上 $$$t$$$ 关键时刻的记录,编号从 $$$1$$$ 到 $$$t$$$。每条记录都包含一些城市对之间的双向道路列表,可用于在特定时刻在 Berland 旅行。

你发现了一台时间机器,可以在关键时刻之间传送你。不幸的是,您无法选择最终到达哪个时间点,但您知道由 $$$k$$$ 时间点 $$$a_{i}$$$ 组成的顺序,机器将按照该顺序运送您。由于两次旅行之间的时间间隔很小,当你发现自己处于下一个关键时刻(包括上次时间旅行之后)时,你最多可以在该时刻沿现有的一条道路行驶,从时间旅行之前所在的城市出来。

目前,你在城市$$$1$$$,时光机已经将你传送到了时刻$$$a_{1}$$$。您想尽快到达城市$$$n$$$。确定到达城市 $$$n$$$ 所需的最少时间旅行次数(包括第一次)。

输入

第一行包含两个整数 $$$n$$$ 和 $$$t$$$ ($$$2 \le n \le 2 \cdot 10^5, 1 \le t \le 2 \cdot 10^5$$$)——伯兰的城市数量和历史关键时刻的记录数量。然后是每条 $$$t$$$ 记录的描述。

每个记录描述的第一行包含一个整数 $$$m_{i}$$$ ($$$0 \le m_{i} \le \min \left(\frac{n(n-1)}{2}, 2 \cdot 10^5\right)$$$) — 第 $$$i$$$ 记录中的道路数量。

接下来的 $$$m_i$$$ 行包含两个整数 $$$v_{j}$$$ 和 $$$u_{j}$$$ ($$$1 \le v_{j}, u_{j} \le n$$$, $$$v_{j} \neq u_{j}$$$) — 由第 $$$j$$$ 条道路连接的城市数量历史上第$$$i$$$个关键时刻。

下一行包含一个整数 $$$k$$$ ($$$1 \le k \le 2 \cdot 10^5$$$) — 发生运动的时间间隔数。

下一行包含 $$$k$$$ 整数 $$$a_1, a_2, \ldots, a_k$$$ ($$$1 \le a_{i} \le t$$$) - 每次运动后您所处的时刻。

保证$$$m_{i}$$$之和不超过$$$2 \cdot 10^5$$$。保证每个无序对 $$$(u, v)$$$ 在一条记录的道路描述中出现不超过一次。

输出

输出一个整数 - 从城市 $$$1$$$ 到达城市 $$$n$$$ 所需的最少时间旅行次数,如果不可能,则输出 $$$-1$$$。

请注意,移动到时刻 $$$a_{1}$$$ 也被视为移动。

示例

输入 #1

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

输出 #1

5

输入 #2

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

输出 #2

-1

注意

在第一个示例中,您位于城市 $$$1$$$ 并移动到时刻 $$$a_{1} = 2$$$。由于没有合适的道路可供通过,因此您什么也不做,并移动到 $$$a_{2} = 1$$$ 时刻,之后您沿着道路 $$$(1, 2)$$$ 行驶。移动到时刻 $$$a_{3} = 2$$$,您沿着道路 $$$(2, 3)$$$ 行驶。移动到 $$$a_{4} = 1$$$ 时刻,您留在城市 $$$3$$$ 并进行下一次时间旅行。在时刻 $$$a_{5} = 2$$$,您沿着道路 $$$(3, 5)$$$ 行驶,经过 $$$5$$$ 时间旅行后到达最终城市。

在第二个示例中,可以证明在给定的时间旅行中不可能到达城市$$$5$$$。