P8124 [BalticOI 2021] From Hacks to Snitches (Day1)

给定一个 $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 解释 第 $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](https://boi.cses.fi/files/boi2021_day1.pdf)。