Sufiks avtomatı
Suffix avtomatı üçün w sətri, Suff(w) dilini qəbul edən deterministik sonlu avtomat A adlanır - yəni w sözünün bütün sonluqlarının çoxluğu. Məsələn, abbab sözünün suffix avtomatı dəqiq olaraq bu sözləri qəbul etməlidir: {abbab, bbab, bab, ab, b, ε}. Biz həmçinin tələb edirik ki, suffix avtomatında əlçatmaz vəziyyətlər olmasın və qəbul edilə bilən vəziyyətlərə çatmaq mümkün olmayan vəziyyətlər mövcud olmasın. Digər məhdudiyyətlər, məsələn, minimalizm, tətbiq olunmayacaq.
Şəkildə abbab sözünün suffix avtomatı göstərilmişdir.
Verilmiş sözün suffix avtomatının sümüyü əsasında suffix avtomatını bərpa etmək lazımdır. Yəni, sizə vəziyyətlər, keçidlər, başlanğıc vəziyyət və qəbul edilə bilən vəziyyətlər verilir. Lakin kənarların üzərindəki işarələr silinmişdir.
Sizdən tələb olunur ki, verilmiş suffix avtomatının kənarlarında işarələri elə yerləşdirəsiniz ki, o, müəyyən bir söz w üçün suffix avtomatı olsun və həmçinin bu sözü tapasınız. Sadəlik üçün qəbul edək ki, əlifbanın ölçüsü heç bir məhdudiyyətə malik deyil, siz simvollar kimi 1 -dən k-ya qədər olan rəqəmləri istifadə edə bilərsiniz (k-nı özünüz seçə bilərsiniz).
Giriş verilənləri
Giriş faylının ilk sətri üç tam ədəd ehtiva edir: n, m və t - vəziyyətlərin sayı, keçidlərin sayı və qəbul edilə bilən vəziyyətlərin sayı, müvafiq olaraq (2 ≤ n ≤ 200, 1 ≤ m ≤ 1000, 1 ≤ t ≤ n). İkinci sətir t tam ədəd ehtiva edir - qəbul edilə bilən vəziyyətlərin nömrələri (vəziyyətlər 1-dən nömrələnir, başlanğıc vəziyyətin nömrəsi 1-dir).
Növbəti m sətir keçidləri təsvir edir: hər bir sətir iki tam ədəd s_i və t_i ehtiva edir və s_i-dən t_i-yə keçidləri təsvir edir.
Çıxış verilənləri
Çıxış faylının ilk sətrində iki tam ədəd l və k yazın - sözün w uzunluğu və əlifbanın ölçüsü. Əlifbanın elementləri kimi {1, ..., k} rəqəmlərindən istifadə edin. k m-dən çox olmamalıdır.
İkinci sətir l tam ədəd ehtiva etməlidir - söz w.
Nəhayət, üçüncü sətir m tam ədəd ehtiva etməlidir - avtomatın sümüyündəki keçidlərin üzərindəki işarələr, giriş faylında təsvir edildiyi sırada.
Cavabın həmişə mövcud olduğu təmin edilir.
Qeyd
