由于你无法靠参加计算机科学竞赛的奖金维持生计，你决定投身艺术行业——更准确地说，你选择了一家特定的博物馆作为你作为艺术大盗的出道之地。不幸的是，这家博物馆守卫森严：有 $K$ 名守卫在楼内巡逻，每名守卫都在博物馆内沿着各自简单的闭合路径巡逻。

为了协调你的行动，你使用了一张地图，该地图将博物馆描述为一组连接 $N$ 个路口的 $M$ 条走廊，路口编号从 $1$ 到 $N$。你从路口 $1$ 出发，而你的目标——一件珍贵的展品——位于路口 $N$。当然，人们可以从任何路口到达博物馆的任何其他路口，但你不确定是否可以在不被发现的情况下做到这一点，也就是说，在不与守卫处于同一路口且不在走廊中与守卫擦肩而过的情况下。

幸运的是，你弄到了守卫值班表。因此，你知道每名守卫在开始时的位置以及他所走的路线。每一分钟，守卫都会从他当前的位置移动到他路线上的下一个路口，而你可以选择停留在当前路口或移动到相邻的路口。你观察到，没有两名守卫的路线相交，且你的起始位置和目标位置都不在任何守卫的路线中。

编写一个程序，利用这些信息计算你安全到达目标*所需的最短时间（以分钟为单位），或者判定这是不可能的。

输入格式

输入的第一行包含上述整数 $N$ 和 $M$。接下来的 $M$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le N, u \neq v$)，表示有一条走廊直接连接路口 $u$ 和 $v$。保证任意两个给定的路口之间最多只有一条走廊直接相连。

下一行包含上述单个整数 $K$。随后有 $K$ 行；其中第 $i$ 行包含一个整数序列，描述第 $i$ 名守卫的路线如下：第一个整数 $\ell_i$ 给出了路线上的不同路口数量。然后是 $\ell_i$ 个两两不同的整数 $v_1, \dots, v_{\ell_i}$，指定了守卫在其路线上经过的路口序列。更准确地说，守卫从路口 $v_1$ 开始，一分钟后他将到达 $v_2$，以此类推；在 $\ell_i$ 分钟后，他将再次回到 $v_1$。

输出格式

你的程序应输出一行。这应包含一个整数，即你安全到达目标所需的最短时间（以分钟为单位），如果无法实现，则输出字符串 impossible。

数据范围

我们始终有 $1 \le N \le 250\,000$，$1 \le M \le 3\,000\,000$，$3 \le \ell_i \le 1\,500$，且 $\ell_1 + \dots + \ell_K \le 2\,750$。

• 子任务 1 (5 分)：$N, M \le 100\,000$，$K = 1$，$\ell_1 \le 125$
• 子任务 2 (10 分)：$N, M \le 100\,000$，$\ell_1 + \dots + \ell_K \le 125$，且没有走廊连接两名不同守卫的路线。
• 子任务 3 (10 分)：$\ell_i \le 200$，$\ell_1 + \dots + \ell_K \le 350$，且没有走廊连接两名不同守卫的路线。
• 子任务 4 (10 分)：没有走廊连接两名不同守卫的路线。
• 子任务 5 (25 分)：$\ell_1 + \dots + \ell_K \le 125$
• 子任务 6 (20 分)：$\ell_i \le 200$，$\ell_1 + \dots + \ell_K \le 350$
• 子任务 7 (20 分)：无其他限制。

• 一旦你到达展品处，你将打开窗户，利用你在全国计算机科学竞赛中赢得的精美翼装离开博物馆，因此无需规划安全的返回路线。 † 当然，你是一位永远不会对守卫动手的绅士大盗！

样例

样例输入 1

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

样例输出 1

4

样例输入 2

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

样例输出 2

5

样例输入 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

样例输出 3

impossible

说明

下图对应上述第一个样例的情况：

此处，守卫开始时所在的路口以粗体显示，他的路线由脚印标出。对你来说，一条最优路线如下：你在起始位置（路口 1）等待一分钟，然后前往路口 2、5，最后毫无延迟地到达 6。第二个样例具有相同的博物馆布局，但守卫的起始位置和方向不同。一条可能的最优路线：从 1 前往 2、3、4、5，最后到达 6。