可怜的 Eve 总是最后一个下班。不幸的是，她非常怕黑，公司规定最后一个离开办公室的人必须确保办公室里所有的灯都关掉。她粗心的同事们有时会忘记关灯，说实话这种情况经常发生，但平心而论，这并不像你想象的那么简单。在 Eve 的办公室里，每个房间恰好有一盏灯，但可能有多个电灯开关。问题在于，与传统的电灯开关不同，这些开关控制的是办公室里一组灯的开关状态。每个开关都会反转一组特定灯的状态（从亮变灭，或从灭变亮），具体取决于开关的设置。甚至可能出现某个房间的灯不受该房间内任何开关影响的情况，或者房间里根本没有开关。

Eve 是一个习惯性很强的人，她每天晚上都想走一条固定的路线离开办公室。同时，每天需要熄灭的灯的集合可能不同，所以她必须为各种可能性做好准备。换句话说，Eve 希望找到一条穿过办公室的路线，使得对于任何可能的灯光配置，她所经过的房间里的开关组合都能让她关掉那种配置下的所有灯。

注意，某些灯光配置可能根本无法熄灭（例如，在样例 1 中，不可能只关掉 0 号灯），但 Eve 不必担心这些配置（因为它们也不可能被点亮）。这条路线只需要让她能够关掉那些实际上可以被关掉的配置即可。Eve 不介意经过一个灯已经熄灭的房间，例如，即使这意味着最后要穿过几个熄灭的房间，只要办公室里的最后一盏灯在路线中途被关掉也是可以的。

图片来自 Comfreak (pixabay), cc0

输入格式

输入的第一行包含三个正整数 $n, m$ 和 $l$ ($2 \le n \le 20, 1 \le m \le 190, 1 \le l \le 100$)，其中 $n$ 是办公室的房间数，$m$ 是房间之间的连接数，$l$ 是开关的数量。接下来 $m$ 行，每行描述一对相邻的房间，包含两个房间编号 $a \neq b$，表示你可以从房间 $a$ 进入房间 $b$，反之亦然。无序对 $\{a, b\}$ 不会出现超过一次。

接下来 $l$ 行，每行描述一个电灯开关。每行开头是一个房间编号，表示该开关所在的房间。行中的第二个整数 $p > 0$ 表示该开关控制的灯的数量。该行的其余部分包含 $p$ 个房间编号。你可以假设在一个开关的控制列表中，不会有两个相同的房间标识符。

房间编号从 $0$ 到 $n - 1$。Eve 离开办公室的出口是 $0$ 号房间，Eve 的起始房间是 $1$ 号房间。你可以假设从 $1$ 号房间可以到达任何其他房间。

输出格式

输出一行，表示从 Eve 的房间到出口房间的路径上最少的房间数（包含两个端点），该路径需要包含一组开关，使得能够关掉任何可能亮着的灯的子集。注意，她可能需要多次访问同一个房间，在这种情况下，每次访问都应计入总数。

样例

输入 1

6 5 7
0 2
2 3
3 4
3 5
1 2
1 2 0 1
1 2 1 2
2 2 2 3
3 2 3 4
4 2 4 5
4 2 0 5
5 2 0 3

输出 1

7