题目描述

Alice and Bob are playing a board game. The board is divided into positions labeled $a, b, c, d, \dots$ and the players use a gamepiece to mark the current position. Each round of the game consists of two steps:

Alice makes a choice. Depending on the current position, she has different options, where each option is a set of positions. Alice chooses one set $S$ among the available sets of positions.

Bob makes a choice. His choice is one position $p$ from the set $S$ that Alice chose in step 1. Bob moves the gamepiece to position $p$, which is the position for the start of the next round.

Prior to the first round, each player independently selects one of the positions and reveals it at the start of the game. Bob’s position is where the game starts. Alice wins the game if she can force Bob to move the gamepiece to the position she has chosen. To make things interesting, they have decided that Bob will pay Alice a certain amount if he loses, but Alice must pay Bob a certain amount after every round. The game now ends if Alice’s position is reached or when Alice runs out of cash.

Both Alice and Bob play optimally: Alice will always choose an option that will lead to her winning the game, if this is possible, and Bob will always try to prevent Alice from winning.

For all possible start and end positions, Alice would like you to determine whether she can win the game and if so, how many rounds it will take.

输入格式

The input consists of a single test case. The first line contains the number of positions $n$ ($1 \leq n \leq 25$). The $n$ positions are labeled using the first $n$ letters of the English alphabet in lowercase. The rest of the test case consists of $n$ lines, one for each position $p$, in alphabetical order. The line for position $p$ contains the options available to Alice in position $p$. It starts with the number of options $m$ ($1 \leq m < 2^ n$), which is followed by $m$ distinct strings, one for each option. Each string contains the positions available to Bob if Alice chooses that option. The string has at least $1$ character, the characters (which correspond to valid board positions) are in alphabetical order, and no characters are duplicated. The total number of options for the test case is at most $10^6$.

输出格式

For each position $p$ in alphabetical order, display one line. In that line, for each position $q$ in alphabetical order display the minimal number of rounds in which Alice can be guaranteed to arrive at position $q$ when starting the game in position $p$, or $-1$ if Alice cannot be guaranteed to reach $q$ from $p$.

题目大意

题目描述

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

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

提示

Time limit: 5000 ms, Memory limit: 1048576 kB.

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