Suffiks pulemyotu#2765

Suffiks pulemyotu

2 saniyə

64 meqabayt

Çətin

Ya zaçot, ya da avtomat.___________________

Hannibal Rektor

Possiltum ordusunun nəzəri hazırlığına yalnız hərbi hüquq deyil, həmçinin kriptoqrafiyanın əsasları da daxil idi. Bu mühazirələri mayor Meqa Bayt oxuyurdu və o, əsgər zarafatından çəkinmirdi. Qvido və Nunçio, üzərinə Possiltum ordusunu içəridən dağıtmaq tapşırığı verilmişdi, terminologiyada çaşqınlıq yaradaraq bundan istifadə etməyə qərar verdilər. Növbəti mühazirənin əvvəlində Nunçio əlini qaldırdı və soruşdu:

- Keçən mühazirədə sonlu avtomatlar haqqında danışdınız. Bəs sonlu pulemyotlar barədə danışacaqsınız?

Meqa Bayt özünü itirmədi.

- Suffiks pulemyotu — bu verilmiş sətrin bütün suffikslərini (sıfırdan $L$ -ə qədər, burada $L$ sətrin uzunluğudur) və yalnız onları qəbul edən sonlu avtomatdır. Serjant Qvido!

- Mən, cənab mayor!

- Siz avtomatı pulemyotdan ayıra bilərsinizmi?

- Əlbəttə, cənab mayor!

- Sizə sonlu avtomat verilib. Onun verilmiş sətrin suffiks pulemyotu olub olmadığını yoxlamaq tələb olunur.

Təəssüf ki, belə bir proqram yazmaq Qvido və Nunçionun vəzifələrinə daxil deyildi, həmçinin Sindikatta və M.İ.F şirkətində də belə deyildi. Ona görə də uyğun proqramı yazmaq Sizin öhdənizə düşür.

Giriş

Giriş faylında bir və ya bir neçə test dəsti verilir. Hər bir dəstin birinci sətrində avtomatın vəziyyət sayısı $N$ , keçid sayı $M$ və qəbul edən vəziyyət sayı $T$ ( $1 \leq T \leq N \leq 50000$ 1 \leq T \leq N \leq 50000, $1 \leq M \leq 100000$ 1 \leq M \leq 100000) verilir. İkinci sətirdə ardıcıl artan qaydada qəbul edən $T$ müxtəlif vəziyyətin nömrələri ( $1$ -dən $N$ -ə qədər) boşluqla ayrılmış şəkildə göstərilir. Sonrakı $M$ sətirdə keçidlər $a_{i} b_{i} c_{i}$ a_i\ b_i\ c_i formasında verilir, burada $1 \leq a_{i}, b_{i} \leq N$ 1 \leq a_i, b_i \leq N, $c_{i}$ c_i isə latın əlifbasının kiçik hərfidir. $a_{i}$ a_i vəziyyətindən $b_{i}$ b_i vəziyyətinə $c_{i}$ c_i hərfinə görə keçid aparılır. Hər $a_{i}$ a_i vəziyyəti üçün $c_{i}$ c_i simvoluna görə bir keçid ola bilər. Dəstin sonuncu sətri — avtomatın pulemyot olmalı olduğu $S$ sətridir. O yalnız kiçik latın hərflərindən ibarətdir və uzunluğu $1$ -dən $50000$ -ə qədər ola bilər. Bundan əlavə, bütün $N$ -lərin cəmi və yoxlanacaq sətrlərin uzunluqlarının cəmi $50000$ -dən, bütün $M$ -lərin isə $100000$ -dən çox olmur.

Fayl $N = M = T = 0$ N = M = T = 0 olan qondarma dəstlə tamamlanır.

Avtomatın ilkin vəziyyəti birincidir. Əgər sətrin şərhi zamanı avtomatda uyğun keçid yoxdursa, avtomat işini dayandırır və sətri qəbul etmir. Sətir yalnız bütün keçidlər tapıldıqdan və onların sonunda avtomat qəbul edən vəziyyətdə olarsa qəbul olunur (yolda hansısa qəbul edən vəziyyətə düşülməsi əhəmiyyət daşımır).

Çıxış

Çıxış faylında nümunədə göstərilən formata uyğun olaraq, avtomatın pulemyot olub olmadığını göstərin.

Nümunələr

Nümunə 1