Game with a Finite Automaton#5399
Everyone knows that playing with finite automata can lead to unexpected outcomes. However, Dmytryk did not quite realize this and, while working on his course project on finite automata, invented a new and intriguing game for two players. The game became so addictive that all his classmates played it for days, neglecting to submit their course projects on finite automata :)
The rules of this game are straightforward. Two players take turns using a deterministic finite automaton with states and an alphabet of symbols. During the game, each player adds exactly one symbol to the string , which starts off empty. If, after a player's move, the automaton accepts the string , that player wins.
Dmytryk believes that it is possible to determine the winner with optimal play from both players in O(m \cdot n) time for a finite automaton. Your task is to write a program that identifies the winner when both players play optimally.
The first line contains (1 \le n \le 10^4) — the number of states in the automaton, and (1 \le m \le 10) — the size of the alphabet. States are numbered from , and the initial state is . The next lines describe the transition function. Each line contains numbers from to n-1. Then comes a line containing — the number of accepting states. The last line contains numbers — the accepting states. The initial state is not an accepting state.
If the game is meaningless (that is, the language of the automaton is empty), output "Automata language is empty." (without quotes). If the game ends in a draw with optimal play, output "Game is a draw.". If the first player wins, output "Dimochka wins.", otherwise output "Dimochka loses.". If there is a win (by either player), print on the second line the shortest length of a string that leads to a win, assuming both play optimally.
Example 1