310783: CF1887B. Time Travel
Description
Berland is a country with ancient history, where roads were built and destroyed for centuries. It is known that there always were $n$ cities in Berland. You also have records of $t$ key moments in the history of the country, numbered from $1$ to $t$. Each record contains a list of bidirectional roads between some pairs of cities, which could be used for travel in Berland at a specific moment in time.
You have discovered a time machine that transports you between key moments. Unfortunately, you cannot choose what point in time to end up at, but you know the order consisting of $k$ moments in time $a_{i}$, in which the machine will transport you. Since there is little time between the travels, when you find yourself in the next key moment in time (including after the last time travel), you can travel on at most one existing road at that moment, coming out from the city you were in before time travel.
Currently, you are in city $1$, and the time machine has already transported you to moment $a_{1}$. You want to reach city $n$ as quickly as possible. Determine the minimum number of time travels, including the first one, that you need to make in order to reach city $n$.
InputThe first line contains two integers $n$ and $t$ ($2 \le n \le 2 \cdot 10^5, 1 \le t \le 2 \cdot 10^5$) — the number of cities in Berland and the number of records about key moments in history. Then follows the description of each of the $t$ records.
The first line of each record description contains a single integer $m_{i}$ ($0 \le m_{i} \le \min \left(\frac{n(n-1)}{2}, 2 \cdot 10^5\right)$) — the number of roads in the $i$-th record.
Each of the next $m_i$ lines contains two integers $v_{j}$ and $u_{j}$ ($1 \le v_{j}, u_{j} \le n$, $v_{j} \neq u_{j}$) — the numbers of cities connected by the $j$-th road in the $i$-th key moment in history.
The next line contains a single integer $k$ ($1 \le k \le 2 \cdot 10^5$) — the number of time moments between which movements will occur.
The next line contains $k$ integers $a_1, a_2, \ldots, a_k$ ($1 \le a_{i} \le t$) — the time moments at which you will be after each movement.
It is guaranteed that the sum of $m_{i}$ does not exceed $2 \cdot 10^5$. It is guaranteed that each unordered pair $(u, v)$ occurs in the road description for one record no more than once.
OutputOutput a single integer — the minimum number of time travels required to reach city $n$ from city $1$, or $-1$ if it is impossible.
Note that movement to time moment $a_{1}$ is also considered a movement.
ExamplesInput5 2 4 1 2 2 3 3 4 4 5 2 2 3 3 5 6 2 1 2 1 2 1Output
5Input
5 2 3 1 2 3 1 4 3 2 2 1 4 5 5 1 2 1 1 1Output
-1Note
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.
Output
贝尔兰是一个有着悠久历史的国家，其道路在几个世纪中被建造和破坏。已知贝尔兰总是有 $ n $ 个城市。你有关于这个国家历史的 $ t $ 个关键时刻的记录，从 $ 1 $ 到 $ t $ 编号。每条记录都包含一些城市对之间的双向道路列表，这些道路在特定的时间点可以用于在贝尔兰旅行。
你发现了一台可以在关键时刻之间传送你的时间机器。不幸的是，你无法选择结束的时间点，但你知道机器将传送你的 $ 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 $) —— 第 $ i $ 条历史关键时刻连接第 $ j $ 条道路的城市编号。
下一行包含一个整数 $ 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 $ 也被认为是一次移动。题目大意： 贝尔兰是一个有着悠久历史的国家，其道路在几个世纪中被建造和破坏。已知贝尔兰总是有 $ n $ 个城市。你有关于这个国家历史的 $ t $ 个关键时刻的记录，从 $ 1 $ 到 $ t $ 编号。每条记录都包含一些城市对之间的双向道路列表，这些道路在特定的时间点可以用于在贝尔兰旅行。 你发现了一台可以在关键时刻之间传送你的时间机器。不幸的是，你无法选择结束的时间点，但你知道机器将传送你的 $ 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 $) —— 第 $ i $ 条历史关键时刻连接第 $ j $ 条道路的城市编号。 下一行包含一个整数 $ 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 $ 也被认为是一次移动。