题目描述

给定一个 $N$ 个点 $M$ 条边的无向图，有 $K$ 个守卫第 $i$ 个守卫会经过 $\ell_i$ 个节点，这 $\ell_i$ 个节点分别为 $v_1,v_2,\cdots,v_{\ell_i}$，运行机制为守卫刚开始位于第 $v_1$ 个节点，设其为第 $0$ 分钟，$1$ 分钟时从第 $v_1$ 个节点走到第 $v_2$ 个节点，$2$ 分钟时从第 $v_2$ 个节点走到第 $v_3$ 个节点，……，$\ell_i-1$ 分钟时从第 $v_{\ell_i-1}$ 个节点走到第 $v_{\ell_i}$ 个节点，$\ell_i$ 分钟时从第 $v_{\ell_i}$ 个节点走到第 $v_1$ 个节点，以此类推，无限循环。

您是一个小偷，您要从第 $1$ 个节点到达第 $N$ 个节点，即 $0$ 分钟时您位于 $1$ 号节点，您可以一个节点直接到另一个节点，但是要经过这两个节点之间的路径，您要保证这条路径上没有一个节点上有守卫，且守卫也不经过这些组成路径的边。您经过每一条边的时间都是一分钟。保证任意两个守卫的路径不相交，并且起点和终点均不在任意守卫的路径上。

您想知道不被守卫发现的情况下需要最短多少分钟或者提出无解。

输入格式

第一行两个整数 $N,M$ 代表点数和边数。

接下来 $M$ 行每行两个整数 $u,v$ 代表一条边。

第 $M+2$ 行一个整数 $K$ 代表守卫个数。

接下来 $K$ 行首先一个整数 $\ell_i$ 代表守卫的路径长度，接下来 $\ell_i$ 个整数 $v_1,v_2,\cdots,v_{\ell_i}$ 描述路径。

输出格式

一行一个整数代表最少需要多少分钟或者无解时输出 impossible。

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

4

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

5

11 13
1 2
2 3
3 4
4 2
3 5
5 6
6 7
7 5
6 8
8 9
9 10
10 8
9 11
3
3 4 2 3
3 7 6 5
3 10 8 9

impossible

提示

样例 1 解释

第 $1$ 个守卫的路径如下：

一种可行方式是：

• $0$ 分钟时，开始在节点 $1$；
• $1$ 分钟时，在节点 $1$ 等待；
• $2$ 分钟时，移动到节点 $2$；
• $3$ 分钟时，移动到节点 $5$；
• $4$ 分钟时，移动到节点 $6$。

样例 2 解释

图和路径与样例 1 一样，只是起点和终点不同。

一种可行方式是，没有等待，直接按照 $1 \to 2 \to 3 \to 4 \to 5 \to 6$ 走。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（5 pts）：$N,M \le 10^5$，$K=1$，$ℓ_1 \le 125$。
• Subtask 2（10 pts）：$N,M \le 10^5$，$\sum ℓ_i \le 125$，满足性质 A。
• Subtask 3（10 pts）：$ℓ_i \le 200$，$\sum ℓ_i \le 350$，满足性质 A。
• Subtask 4（10 pts）：满足性质 A。
• Subtask 5（25 pts）：$\sum ℓ_i \le 125$。
• Subtask 6（20 pts）：$ℓ_i \le 200$，$\sum ℓ_i \le 350$。
• Subtask 7（20 pts）：无特殊限制。
• Subtask Ex（0 pts）：Extra Subtask。

对于 $100\%$ 的数据，$1 \le N \le 2.5 \times 10^5$，$1 \le M \le 3 \times 10^6$，$3 \le ℓ_i \le 1500$，$\sum ℓ_i \le 2750$。

性质 A 为没有一条边连接任意两个守卫的路径。

说明

翻译自 BalticOI 2021 Day1 C From Hacks to Snitches。