Игра с конечным автоматом
Все знают, что шутки с конечными автоматами могут закончиться очень плохо. Однако Димочка понимал это не очень хорошо и в процессе работы над курсовой работой по конечным автоматам придумал новую интересную игру для двух игроков. Игра оказалась настолько увлекательной, что все его однокурсники играли в нее целыми днями… Конечно, никто из них так и не сдал курсовик по конечным автоматам :)
Правила этой игры достаточно просты. Два игрока берут детерминированный конечный автомат с n состояниями и алфавитом из m символов. В процессе игры они добавляют символы (один игрок за один ход добавляет один и ровно один символ) к строке S, которая изначально пуста. Если после чьего-то хода автомат допускает строку S, то этот игрок считается выигравшим.
Димочка думает, что по конечному автомату можно за время O(m·n) определить, кто выиграет при оптимальной игре обоих игроков. Напишите программу, определяющую игрока, выигрывающего при оптимальной стратегии обоих.
Входные данные
Первая строка входного файла содержит n – число состояний автомата (1 ≤ n ≤ 10^4) и m – мощность алфавита конечного автомата (1 ≤ m ≤ 10). Состояния автомата нумеруются с нуля, нулевое состояние является начальным. Далее идут n строк, описывающих функцию переходов конечного автомата. Каждая строка содержит по m чисел от 0до n-1. Далее идет k – число допускающих состояний автомата. Последняя строка содержит k чисел – номера допускающих состояний. Начальное состояние не является допускающим.
Выходные данные
Если игра не имеет смысла (т.е. язык автомата пуст), выведите в выходной файл фразу "Automata language is empty." без кавычек. Если при оптимальной стратегии обоих игроков игра закончится вничью, выведите "Game is a draw.". Если выигрывает первый игрок, выведите фразу "Dimochka wins.", иначе – выведите "Dimochka loses.". В случае выигрыша одного из игроков во второй строке выведите наименьшую длину строки, которая приводит к выигрышу (при оптимальной игре обоих).