#include<bits/stdc++.h>
using namespace std;
const int N = 5e6 + 10, inf = 1e9;
vector<int>g[N], del, ng;
int fr[N], bel[N], id[N], w[N], dis[N], vis[N], sz[N], is[N];
struct node
{
	int x, t, d;
	friend bool operator < (const node &a, const node &b){return a.d>b.d;}
};
priority_queue<node>pq;

void upd(int x, int t)
{
	int p = w[x-1] + 1 + t % sz[bel[x]];
	if(t<dis[p]) dis[p] = t, pq.push((node){x,t%sz[bel[x]],t});
}

int main()
{
	int n, m, i, j, a, b;
	scanf("%d%d", &n, &m);
	while(m--) scanf("%d%d", &a, &b), g[a].emplace_back(b), g[b].emplace_back(a);
	int k;scanf("%d", &k);
	for(i=1;i<=k;i++)
	{
		scanf("%d", &sz[i]);
		for(j=0;j<sz[i];j++) scanf("%d", &a), bel[a] = i, id[a] = j;
	}
	sz[0] = 1;
	for(i=1;i<=n;i++) w[i] = w[i-1] + sz[bel[i]];
	for(i=2;i<=w[n];i++) dis[i] = inf;
	pq.push((node){1,0,0});
	while(!pq.empty())
	{
		int d = pq.top().x, p = pq.top().t;pq.pop();
		if(vis[w[d-1]+p+1]) continue;
		vis[w[d-1]+p+1] = 1, del.clear();
		int t = dis[w[d-1]+p+1];
		if(bel[d]&&id[d]!=(t+1)%sz[bel[d]]) upd(d,t+1);
		//printf("%d %d %d\n", d, p, t);
		for(auto y:g[d])
		{
			int z = bel[y];
			if(!bel[d])
			{
				if(z)
				{
					if((t+1)%sz[z]!=id[y]) upd(y,t+1);
					int tt = t + (id[y] - t % sz[z] + sz[z]) % sz[z];
					upd(y,tt+1);
				} else upd(y,t+1);
			} else if(!z) upd(y,t+1), del.emplace_back(y);
			else
			{
				int r = (id[y] - id[d] + sz[z]) % sz[z];
				if(r==1&&bel[d]==z) upd(y,t+1);
				else if(r==sz[z]-1&&bel[d]==z)
				{
					if(id[y]!=(t+1)%sz[z]&&id[y]!=t%sz[z]) upd(y,t+1);
				}
				else
				{
					if((t+1)%sz[z]!=id[y]) upd(y,t+1);
					int T = t + (id[y] - t % sz[z] + sz[z]) % sz[z];//注意这里可能在 x 的时候
					if(T%sz[bel[d]]!=id[d]) upd(y,T+1), del.emplace_back(y);
					else
					{
						int t1 = T + (t - T % sz[bel[d]] + sz[bel[d]]) % sz[bel[d]];
						int T1 = t1 + (id[y] - t1 % sz[z] + sz[z]) % sz[z];
						if((t1+1)%sz[z]!=id[y]) upd(y,t1+1);
						if(T1%sz[bel[d]]!=id[d]) upd(y,T1+1);
					}
				}
			}
		}
		for(auto i:del) is[i] = 1;
		ng.clear();
		for(auto i:g[d]) if(!is[i]) ng.emplace_back(i);
		swap(g[d],ng), ng.clear();
		for(auto i:del) is[i] = 0;
	}
	if(dis[w[n]]==inf) printf("impossible\n");
	else printf("%d\n", dis[w[n]]);
	return 0;
}

太难了太难了太难了。

• 复杂度分析，拆点，定义域值域互换，最短路形优化 dp 转移。

显然你可以估计答案的上界，然后有一个 $p(u,t)\in\lbrace0,1\rbrace$ 表示 $t$ 时刻在 $u$ 是否可行。定义 $l_u$ 表示 $u$ 所在的限制路径长度。考虑 $u$ 是否在某个限制环上，对于 $u$ 不在限制路径上的情况，$p(u,t)=1$ 的 $t$ 不存在或者是一段后缀；在限制路径上的情况，对于 $l$ 同余的 $t$ 要么不存在 $1$ 要么是一段后缀。那么可以定义域值域互换，设计 $f_{u,i}$ 表示到达 $u$ 时刻模 $l$ 为 $i$ 的最小时刻，如果不在限制路径上 $l=+\infty$。考虑一下 $f_{u,s}\to f_{v,t}$ 的转移，要求 $u=v$ 或者 $(u,v)\in E$，且 $t$ 时刻没有怪兽在 $v$，且 $t$ 时刻没有 $v\to u$ 的怪兽。那么就是，$\min_{k\in \N}(f_{u,s}+kl_u+1)$ 使得 $f_{u,s}+kl_u+1\equiv t(\bmod l_v)$。如果 $u,v$ 同环就要求，不允许 $t-1$ 时刻是 $v$ 且 $t$ 时刻是 $u$。令 $L=\sum ℓ_i$，直接做的复杂度会高达 $\mathcal O(L^4+mL)$，这是计算转移的数目得出的。具体使用 dijkstra 来转移。我们的目标是减少无效转移数量。只保留有效的转移。

对转移具体分类讨论：

• $u,v$ 均不在限制环上：可以直接 dijkstra 转移，这样的 $(u,v)$ 只用转移一次；事实上同理的，$v$ 不在限制环但 $u$ 在限制环是相同的。该类转移总复杂度 $\mathcal O(m)$。
• $u$ 不在限制环但 $v$ 在限制环的情况：我们希望减少无效的转移。注意到对于 $u$ 等待 $t_1+t_2$ 时刻到 $v$ 在某些情况下可以转化成 $u$ 等待 $t_1$ 时刻再到 $v$ 等待 $t_2$ 时刻。那么我们希望将大部分 $u\to v$ 的转移转化成后者，那么考虑 $k=(t_1+t_2)$ 无法被转化的情况，就是中间无法避开守卫的情况。找到最小的 $nxt$ 表示在严格大于 $f_u$ 之后第一个被守卫经过的时刻，那么我们可以只转移：$t=f_u+1$ 以及 $t=nxt+1$。注意 $f_u+1=nxt$ 时是无法执行前者的转移的。该类转移总复杂度 $\mathcal O(m)$。

说明一下：如果一条边是理论最优的，可以从边的备选集合中删除。

• $u,v$ 均在限制环的情况，需要考虑 $u,v$ 是否同环。如果 $u,v$ 同环，注意特殊性质保证了只存在该类转移。分讨一下正序和逆序，用类似上一类的思想，对于 $f_{u,s}$ 可以向 $\mathcal O(1)$ 个 $f_{v,t}$ 进行转移。也就是说，在具体转移时只需要考虑 $k=0$ 的情况。即最小时刻即为需要考虑的。该类转移总复杂度 $\mathcal O(L^2)$。
• 重点在于 $u,v$ 均在限制环并且 $u,v$ 不同环的情况。我们想要干的事情是：对于两个相邻的不同环 $a,b$，将转移的次数控制在 $\mathcal O(ℓ_aℓ_b)$。类似的，我们考虑 $nxt$ 表示在环 $v$ 上 $f_{u,s}+1$ 的后继。与之不同的是，我们并不能毫无顾忌的在 $u$ 上一直等待，否则可能会碰见怪兽。考虑在 $nxt$ 时刻时环 $u$ 的位置上并没有怪兽。那么你可以提前到 $v$ 然后立刻到 $u$ 进行一个折返，这样就可以转移到 $v$ 更后面的状态。此时这个转移时理论最优的，因此可以删去；
• 如果 $nxt$ 时刻 $u$ 有怪兽，那么尽管对于 $nxt$ 之前的 $f_{v,t}$ 可以执行转移，但是对于 $nxt$ 及以后的状态而言，考虑找到 $P$ 时刻表示 $nxt$ 之后首个模 $l_u$ 为 $s$ 的时刻，对于 $P$ 类似的找像 $nxt$ 一样的后继 $Q$，判定 $Q$ 时刻时 $u$ 位置是否有怪兽，执行正常的转移。我们想要说明的是，转更多圈是没有意义的：这个情形是循环坠入的，转更多圈得到的情况与此相同。注意，此时边 $u\to v$ 的转移不一定理论最优，因此不能从边的备选集合中删去。

考虑分析一下不同环间转移的复杂度：对于第一次找 $nxt$ 的 $l_b$ 组可以消除到剩余最多 $(l_b/l_a)$ 条边，但是对于第二次虽然会造成 $(l_a-1)$ 个状态的访问，但是只会访问这么多。因此对于一个点向下一个考虑是 $\leq 2l_b$ 个的。乘以 $l_a$ 就是 $\mathcal O(ℓ_aℓ_b)$ 的环间转移。求和可以得到 $\mathcal O(m\log m+L^2)$ 的复杂度。