E. Time Travel

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

Input

The 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.

Output

Output 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.

Examples

input

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

output

5

input

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

output

-1

Note

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.

解题思路

  补题的时候做出来了，思维难度不大。

  题目读了半天，大概是说有 $n$ 个点，$t$ 个记录，每个记录分别对应不同的无向图。同时给你一个大小为 $k$ 的时间序列 $a$，$a_i$ 表示第 $i$ 个时刻的图是第 $a_i$ 个记录所表示的无向图。每个时刻可以选择从当前点移动到相邻点（此刻的图中这两点有直接边相连）或不动，你初始时在 $1$ 号点，问从 $1$ 号点到 $n$ 号点的最早（小）时刻是多少。

  难点就在建图上。现在有 $t$ 个图（记录），我们直接统一成一个图来表示，只需标记每条边属于哪个记录即可。与一般的最短路问题定义一样，用 $\text{dist}_{u}$ 表示从 $1$ 到 $u$ 的最早时刻。假设有边 $(u,v)$，属于第 $\text{id}_{(u,v)}$ 个记录，由于到点 $u$ 的最早时刻已经是 $\text{dist}_u$ 了，因此经过 $u$ 到 $v$ 的最早时刻必然要大于 $\text{dist}_u$，那么我们就在 $a$ 里所有是 $a_i = \text{id}_{(u,v)}$ 的时刻中，找到大于 $\text{dist}_u$ 的最小时刻 $w$，如果 $w$ 存在且 $\text{dist}_v > w$，那么我们就更新 $\text{dist}_v = w$。

  对此我们可以开个 $t$ 个 $\text{std::set}$ 来分别存储某个记录都对应哪些时刻，那么就可以通过二分来找到大于 $\text{dist}_u$ 的最小时刻。而最短路算法的话可以用 Dijkstra，正确性证明如下：假设 $u$ 是所有还没确定最小时刻的点中，到达时刻最小的点，那么对于任意一个也没确定的点 $v$，必然有 $\text{dist}_u \leq \text{dist}_v$，而如果存在某个 $v$ 可以更新 $u$，那么必然会有 $w > \text{dist}_v \geq \text{dist}_u$，因此 $u$ 必然下一个可以确定的点，Dijkstra 正确性得证。

  AC 代码如下，时间复杂度为 $O(m(\log{k} + \log{m}))$：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e5 + 10, M = N * 2;

int head[N], e[M], id[M], ne[M], idx;
set<int> st[N];
int dist[N];
bool vis[N];

void add(int u, int v, int w) {
    e[idx] = v, id[idx] = w, ne[idx] = head[u], head[u] = idx++;
}

int main() {
    int n, m, k;
    scanf("%d %d", &n, &m);
    memset(head, -1, sizeof(head));
    for (int i = 1; i <= m; i++) {
        int cnt;
        scanf("%d", &cnt);
        while (cnt--) {
            int u, v;
            scanf("%d %d", &u, &v);
            add(u, v, i), add(v, u, i);
        }
    }
    scanf("%d", &k);
    for (int i = 1; i <= k; i++) {
        int x;
        scanf("%d", &x);
        st[x].insert(i);
    }
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push({0, 1});
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = head[u]; i != -1; i = ne[i]) {
            auto it = st[id[i]].upper_bound(dist[u]);
            if (it != st[id[i]].end() && dist[e[i]] > *it) {
                dist[e[i]] = *it;
                pq.push({*it, e[i]});
            }
        }
    }
    if (dist[n] == 0x3f3f3f3f) dist[n] = -1;
    printf("%d\n", dist[n]);
    
    return 0;
}

参考资料

  Codeforces Round #905 (Div. 1, Div. 2, Div. 3) Editorial：https://codeforces.com/blog/entry/121621