Avtomat#4593
Verilmiş sözünün bütün sonluqlarını qəbul edən deterministik sonlu avtomat qurun (və bəlkə də digər sonlu sözləri də qəbul edə bilər). Avtomat minimal sayda vəziyyətdən — və ən çox keçiddən ibarət olmalıdır. Hər bir vəziyyət avtomatın son vəziyyəti kimi qəbul edilir. Başlanğıc vəziyyətin nömrəsi -dir.
Aşağıda "" sözünün test nümunəsi üçün avtomat göstərilmişdir.
Tək sətirdə sözü (1 \leq |\textbf{s}| \leq 10^{5}), kiçik latın hərflərindən ibarətdir.
Birinci sətirdə iki ədəd və (1 \leq k \leq 2n) — vəziyyətlərin sayı və keçidlərin sayı. Sonra sətir, hər birində iki ədəd a_i, b_i (1 \leq a_i, b_i \leq n) və hərf c_i ('a' \leq c_i \leq 'z'), bu, a_i vəziyyətindən b_i vəziyyətinə c_i hərfi ilə keçidin mövcudluğunu göstərir. Keçidləri istənilən qaydada təqdim edə bilərsiniz. Əgər bir neçə həll varsa, onlardan istənilən birini təqdim edə bilərsiniz.
Nümunə 1