Гра зі скінченним автоматом
Усі знають, що жарки зі скінченними автоматами можуть завершитись дуже погано. Проти Дімочка розумів це не дуже добре і у процесі роботи над курсовою роботою по скінченним автоматам придумав нову цікаву гру для двох гравців. Гра виявилась настільки захоплюючою, що усі його однокурсники грали у неї цілими днями… Звичайно, ніхто з них так і не здав курсовик по скінченним автоматам :)
Правила цієї гри досить прості. Два гравці беруть детермінований скінчений автомат з 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.". У випадку виграшу одного з гравців у другому рядку виведіть найменшу довжину рядка, який призводить до виграшу (при оптимальній грі обох).