Sonlu avtomatla oyun#5399
Hamı bilir ki, sonlu avtomatlarla zarafat pis nəticələnə bilər. Lakin Dimo bunu yaxşı başa düşmədi və sonlu avtomatlarla bağlı kurs işi üçün işləyərkən iki nəfərlik yeni maraqlı oyun uydurdu. Oyun o qədər cəlbedici oldu ki, bütün həmkarları günlərlə onu oynadılar... Əlbəttə, onlardan heç biri kurs işlərini təhvil verə bilmədi :)
Oyunun qaydaları kifayət qədər sadədir. İki oyunçu növbə ilə vəziyyətli və simvollu əlifbası olan deterministik sonlu avtomatla oynayır. Oyun zamanı hər oyunçu başlanğıcda boş olan sətrinə hər dəfə bir simvol əlavə edir. Əgər oyunçudan sonra avtomat sətrini qəbul edirsə, həmin oyunçu qalib gəlir.
Dimo düşünür ki, sonlu avtomat üçün O(m \cdot n) zamanda hər iki oyunçunun optimal oynayacağı halda qalibi müəyyən etmək olar. Sizin vəzifəniz — hər iki oyunçu optimal oynayanda qalibi müəyyən edən proqram yazmaqdır.
Girişin ilk sətri (1 \le n \le 10^4) — avtomatın vəziyyətlərinin sayı və (1 \le m \le 10) — əlifbanın ölçüsüdür. Vəziyyətlər -dan nömrələnir, başlanğıc vəziyyəti -dır. Növbəti sətir avtomatın keçid funksiyasını təsvir edir. Hər sətrdə ədəd var, hər biri -dan n-1-ə qədərdir. Sonra — qəbul edən vəziyyətlərin sayı verilir. Son sətir qəbul edən vəziyyətin nömrələrini ehtiva edir. Başlanğıc vəziyyəti qəbul edən deyil.
Əgər oyun mənasızdırsa (yəni avtomat dili boşdur), çıxışda **"Automata language is empty."** sözlərini (dırnaqsız) verin. Hər iki oyunçu optimal oynayanda oyun heç-heçə bitərsə, **"Game is a draw."** verin. Əgər birinci oyunçu qalib gəlirsə, **"Dimochka wins."**, əks halda — **"Dimochka loses."** verin. Hər iki oyunçu optimal oynayanda qalib gələn oyunçu üçün ikinci sətrdə ən qısa qalibiyyət sətrinin uzunluğunu çıxışa verin.
Nümunə 1