题目描述

题目译自 BalticOI 2021 Day1「From Hacks to Snitches」，译者 Shuchong。

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

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

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

输入格式

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

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

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

接下来 $K$ 行首先一个整数 $ℓ_i$ 代表守卫的路径长度，接下来 $ℓ_i$ 个整数 $v_1,v_2,\cdots,v_{ℓ_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

数据范围与提示

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

• 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）：无特殊限制。

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