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