Задачі
Гра зі скінченним автоматом
Гра зі скінченним автоматом
Усі знають, що жарки зі скінченними автоматами можуть завершитись дуже погано. Проти Дімочка розумів це не дуже добре і у процесі роботи над курсовою роботою по скінченним автоматам придумав нову цікаву гру для двох гравців. Гра виявилась настільки захоплюючою, що усі його однокурсники грали у неї цілими днями… Звичайно, ніхто з них так і не здав курсовик по скінченним автоматам :)
Правила цієї гри досить прості. Два гравці беруть детермінований скінчений автомат з \textbf{n} станами і алфавітом з \textbf{m} символів. У процесі гри вони додають символи (один гравець за один хід додає один і рівно один символ) до рядка \textbf{S}, який спочатку порожній. Якщо після чийогось ходу автомат допускає рядок \textbf{S}, то цей гравець вважається вигравшим.
Дімочка думає, що за скінченним автоматом можна за час \textbf{O(m·n)} визначити, хто виграє при оптимальній грі обох гравців. Напишіть програму, яка визначає гравця, який виграє при оптимальній стратегії обох.
\InputFile
Перший рядок вхідного файлу містить \textbf{n} -- число станів автомата (\textbf{1} ≤ \textbf{n} ≤ \textbf{10^4}) та \textbf{m} -- потіжність алфавіту скінченного автомату (\textbf{1} ≤ \textbf{m} ≤ \textbf{10}). Стани автомату нумеруються з нуля, нульовий стан є початковим. Далі йде \textbf{n }рядків, які описують функцію переходів скінченного автомату. Кожен рядок містить по \textbf{m} чисел від \textbf{0} до \textbf{n-1}. Далі йде \textbf{k} -- число допустимих станів автомату. Останній рядок містить \textbf{k} чисел -- номери допустимих станів. Початковий стан не є допустимим.
\OutputFile
Якщо гра не має змісту (тобто мова автомату порожня), виведіт у вихідний файл фразу "\textbf{Automata language is empty.}" без лапок. Якщо при оптимальній стратегиї обох гравців гра завершиться унічию, виведіть "\textbf{Game is a draw.}". Якщо виграє перший гравець, виведіть фразу "\textbf{Dimochka wins.}", інакше -- виведіть "\textbf{Dimochka loses.}". У випадку виграшу одного з гравців у другому рядку виведіть найменшу довжину рядка, який призводить до виграшу (при оптимальній грі обох).
Вхідні дані #1
2 1 0 1 1 1
Вихідні дані #1
Automata language is empty.