题目描述
"魔法石" 是一种具有惊人力量的传奇物质。这种石头可以将任何金属变成纯金。它还可以产生 Elixir of Life，这将使饮用者不朽。奇洛，一个雄心勃勃，渴望成为富有和不朽的巫师，正在紧急而秘密地寻找这块石头。

最后，奇洛来到了“魔法石”的藏身之处，位于一个秘密的山洞里。这是一个装满箱子的大房间。每个箱子里都有一块魔法石，表面标有魔法石的名字。中间的箱子让奇洛从他的皮肤里跳了出来——它只是被标记了 “魔法石”。

奇洛仔细观察了这个箱子，他发现箱子表面有一些不同的凹面，这意味着需要几颗特定的魔法石才能解锁箱子。如果他在每个凹中放置正确的魔法石，一块石头换一个凹面，他就可以用他的法力打开箱子，把魔法石放在箱子里。

奇洛已经有一些不同的魔法石，但他没有用 “魔法石” 打开箱子所需的所有石头，所以他应该从其他箱子里得到他需要的石头，这些箱子有类似的机制，可以用他已经拥有的石头打开。由于奇洛的法力值有限，他想打开最少数量的宝箱来获得 “魔法石”。

你可以假设奇洛的魔法石是不同的，躺在不同箱子里的魔法石也是不同的。所有放入凹面的魔法石都可以重复使用。

输入
将有几个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $M$（$1 <= N <= 1000$, $1 <= M <= 100$），分别代表巫师拥有的魔法石数量和房间中的箱子数量。以下 $N$ 行中的每一行都包含一个字符串，这是巫师拥有的一块魔法石的名称。在那之后，以下每行 $M$ 行都描述了一个箱子（当然，包括装有 “Sorcerer's Stone” 的箱子）是这样的：

魔法石 1, 魔法石 2, ...魔法石 T: 魔法石 R

这意味着魔法石 $R$ 躺在这个箱子里，需要魔法石 $1$、魔法石 $2$、...、魔法石 $T$ 才能打开箱子（$1 <= T <= 9$）。您应该注意到，Magic Stone $1$ 到 $T - 1$ 后跟一个逗号和一个空格，而 Magic Stone $T$ 后面跟着一个冒号和一个空格。所有魔法石的名称都是字符串，不包括逗号或冒号，且不超过 $20$ 个字符。

$N = M = 0$ 的测试用例将结束输入，不应对其进行处理。

输出
对于每个测试用例，如果巫师能得到 “Sorcerer's Stone”，则输出他需要打开的最小箱子数量；否则输出 -1。

输入数据 1

5 3
Amethyst
Moonstoon
Cat's eye
Diamond
Emerald
Topaz, Cat's eye, Diamond: Zircon
Zircon, Emerald: Sorcerer's Stone
Amethyst: Topaz
5 3
Amethyst
Moonstoon
Cat's eye
Diamond
Emerald
Amethyst: Topaz
Emerald: Zircon
Zircon, Emerald: Sorcerer's Stone
0 0

输出数据 1

3
2

来源
北京 2005 预选赛