题目描述

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

给定一个 $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。

样例 1

输入

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

输出

4

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

一种可行方式是：

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

样例 2

输入

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

输出

5

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

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

样例 3

输入

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 \ell_i \le 1500$
• $\sum \ell_i \le 2750$

子任务：

• Subtask 1（$5$ 分）：$N, M \le 10^5$，$K = 1$，$\ell_1 \le 125$
• Subtask 2（$10$ 分）：$N, M \le 10^5$，$\sum \ell_i \le 125$，满足性质 A
• Subtask 3（$10$ 分）：$\ell_i \le 200$，$\sum \ell_i \le 350$，满足性质 A
• Subtask 4（$10$ 分）：满足性质 A
• Subtask 5（$25$ 分）：$\sum \ell_i \le 125$
• Subtask 6（$20$ 分）：$\ell_i \le 200$，$\sum \ell_i \le 350$
• Subtask 7（$20$ 分）：无特殊限制

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