Гра зі скінченним автоматом#5399
Усі знають, що жарти зі скінченними автоматами можуть завершитися дуже погано. Проте Дмитрик розумів це не дуже добре і, працюючи над курсовою про скінченні автомати, вигадав нову цікаву гру для двох гравців. Гра виявилася настільки захоплюючою, що всі його однокурсники грали в неї днями, забувши здати курсові роботи про скінченні автомати :)
Правила цієї гри досить прості. Два гравці по черзі використовують детермінований скінченний автомат з станами та алфавітом з символів. Під час гри кожен гравець додає рівно один символ до рядка , який спочатку порожній. Якщо після ходу гравця автомат приймає рядок , цей гравець виграє.
Дмитрик вважає, що для скінченного автомата за час O(m \cdot n) можна визначити, хто виграє при оптимальній грі обох гравців. Ваше завдання — написати програму, яка визначає переможця при оптимальній грі обох гравців.
Перший рядок містить (1 \le n \le 10^4) — кількість станів автомата, і (1 \le m \le 10) — потужність алфавіту автомата. Стани автомата нумеруються з , початковий стан — . Далі йде рядків, які описують функцію переходу автомата. У кожному рядку чисел від до n-1. Далі йде рядок з числом — кількість приймаючих станів. Останній рядок містить чисел — номери приймаючих станів. Початковий стан не є приймаючим.
Якщо гра не має сенсу (тобто мова автомата порожня), виведіть фразу "Automata language is empty." без лапок. Якщо при оптимальній грі обох гравців гра закінчиться унічию, виведіть "Game is a draw.". Якщо перемагає перший гравець, виведіть фразу "Dimochka wins.", інакше — "Dimochka loses.". У разі виграшу одного з гравців, на другому рядку виведіть найменшу довжину рядка, що призводить до виграшу (при оптимальній грі обох).
Приклад 1