Winning Strategy

Time limit8sMemory limit128 MB

Summary

For every start and goal pair, find the fewest rounds in which the chooser can force the token to the goal while the opponent picks inside each offered set.

Level: Hard8 of 10
Topics: Game theory, Graph, BFS
Solved: No attempts yet

Problem

A monkey and a dog play a board game on $n$ named positions. Each round:

The monkey chooses one option, a set of positions the dog may move to.
The dog picks one position from that set and moves the token there.

Before play, the monkey picks the goal position and the dog picks the start. The monkey wins if the token reaches the goal. The monkey pays the dog each round, so failure to win eventually bankrupts the monkey.

Both play optimally. For every start $p$ and goal $q$ , find the minimum number of rounds for the monkey to guarantee a win, or $-1$ if impossible.

Input

The first line has $n$ ( $1 \le n \le 25$ ). Positions use the first $n$ lowercase letters.

Each of the next $n$ lines describes one position: option count $m$ ( $1 \le m < 2n$ ) followed by $m$ strings, each a sorted set of letters the dog may choose from on that option.

Output

Print $n$ lines. Line $i$ lists, in position order, the minimum winning rounds from start $i$ to each goal, or $-1$ when the monkey cannot force a win.

Examples1

Example 1
Input
```
2
2 ab b
1 b
```
Expected output
```
0 1
-1 0
```