P6895 [ICPC 2014 WF] Game Strategy

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 希望你确定她是否能够赢得比赛，如果可以，需要多少轮才能赢得比赛。

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

对于每一个 $p$ 单独输出一行。在该行中，按字母顺序输出每个位置 $q$ 表示 Alice 开始游戏时可以保证到达的最小轮次，或者如果 Alice 不能保证从 $p$ 到达 $q$，则显示 $-1$。 ### **说明/提示** 时间限制： $5000$ ms，空间限制：$1048576$ kB。 来源：International Collegiate Programming Contest (ACM-ICPC) World Finals 2014

Time limit: 5000 ms, Memory limit: 1048576 kB. International Collegiate Programming Contest (ACM-ICPC) World Finals 2014