Description

Alice 和 Bob 正在玩一款棋盘游戏。棋盘被分成了标有 $a,b,c,d,...$ 的位置，玩家们使用游戏棋子来标记当前位置。游戏的每一轮包括两个步骤：

Alice 行动。根据当前位置，她有不同的选择，每个选择都是一组位置。Alice 将从可用的位置集合中选择一个集合 $S$。

Bob 行动。他的选择是集合 $S$ 中的一个位置 $p$。Bob 将游戏棋子移动到位置 $p$，这会是下一轮游戏的起始位置。

在第一轮之前，每个玩家独立选择一个位置并在游戏开始时公开位置。Bob 的位置是游戏开始的地方。如果 Alice 能够迫使 Bob 将游戏棋子移动到她选择的位置，Alice 就赢得了比赛。为了使事情更有趣，他们决定如果 Bob 输了，他将支付给 Alice 一定金额，但 Alice 必须在每轮之后向 Bob 支付一定金额。如果 Bob 到达 Alice 的位置或者 Alice 没钱了，游戏就结束了。Alice 和 Bob 都采取最佳策略：如果可能的话，Alice 总是选择会能让她赢得比赛的方案，而 Bob 总是试图阻止 Alice 获胜。对于所有可能的起始和结束位置，Alice 希望你确定她是否能够赢得比赛，如果可以，需要多少轮才能赢得比赛。

Input Format

输入由单组数据组成。第一行包含位置数 $n$ $(1\le n\le 25)$，这些位置用英文小写字母的前 $n$ 个字母标记。接下来 $n$ 行，每行表示位置 $p$，按字母顺序排列。位置 $p$ 这一行包含 $Alice$ 在该位置的可选项。每行首先输入一个数 $m$ $(1 \le m < 2^n)$，后跟 $m$ 个不同字符串，每个字符串表示 Alice 选择该方案时 Bob 可移动到的位置。字符串至少包含 $1$ 个字符，这些字符（对应有效的棋盘位置）按字母顺序排列，没有重复字符。数据的方案总数最多为 $10^6$。

Output Format

对于每一个 $p$ 单独输出一行。在该行中，按字母顺序输出每个位置 $q$ 表示 Alice 开始游戏时可以保证到达的最小轮次，或者如果 Alice 不能保证从 $p$ 到达 $q$，则显示 $-1$。

说明/提示

时间限制： $5000$ ms，空间限制：$1048576$ kB。

来源：International Collegiate Programming Contest (ACM-ICPC) World Finals 2014

2
2 ab b
1 b

0 1 
-1 0

3
1 b
2 b a
2 ab ac

0 1 -1 
1 0 -1 
2 2 0