Sufiks avtomatı#4164
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: \{\textbf{abbab}, \textbf{bbab}, \textbf{bab}, \textbf{ab}, \textbf{b}, \textbf{\varepsilon}\}. Avtomatda əlçatmaz vəziyyətlər olmamalı və qəbul edilə bilən vəziyyətlərə çatmaq mümkün olmayan vəziyyətlər mövcud olmamalıdır. Digər məhdudiyyətlər, məsələn, minimalizm, tətbiq olunmur.
Şəkildə abbab sözünün suffix avtomatı göstərilmişdir.
Verilmiş sözün suffix avtomatının sümüyu ə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ü tapın. 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ş 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 \le n \le 200, 1 \le m \le 1000, 1 \le t \le n). İkinci sətr 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ətr keçidləri təsvir edir: hər bir sətr 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ış 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 \{\textbf{1}, \ldots, \textbf{k}\} rəqəmlərindən istifadə edin. k m-dən çox olmamalıdır.
İkinci sətr l tam ədəd ehtiva etməlidir — söz w.
Üçüncü sətr isə m tam ədəd ehtiva etməlidir — automatin sümüyu üzrə 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.
Nümunə 1
