Game with a Finite Automaton
Everyone knows that playing with finite automata can lead to unexpected outcomes. However, Dimochka didn't quite grasp 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 n states and an alphabet of m symbols. During the game, each player adds exactly one symbol to the string S, which starts off empty. If, after a player's turn, the automaton accepts the string S, that player wins.
Dimochka believes that it's possible to determine the winner with optimal play from both players in O(m·n) time for a finite automaton. Your task is to write a program that identifies the winner with optimal strategies from both players.
Input
The first line of the input contains n – the number of states in the automaton (1 ≤ n ≤ 10^4) and m – the size of the alphabet (1 ≤ m ≤ 10). The states are numbered from zero, with state zero being the initial state. The next n lines describe the transition function of the automaton. Each line contains m numbers ranging from 0 to n-1. Following this, there is a line with k – the number of accepting states. The last line lists k numbers, which are the accepting states. Note that the initial state is not an accepting state.
Output
If the game is meaningless (i.e., the language of the automaton is empty), output "Automata language is empty." without quotes. If the game ends in a draw with optimal play from both players, output "Game is a draw.". If the first player wins, output "Dimochka wins.", otherwise output "Dimochka loses.". In the case of a win by either player, also output the shortest length of the string that leads to a win (assuming optimal play from both) on the second line.