Avtomat
Verilmiş s 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 - n və ən çox 2n 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 1-dir.
Aşağıda "abacaba" sözünün test nümunəsi üçün avtomat göstərilmişdir.
Giriş verilənləri
Tək sətirdə s sözü (1 ≤ |s| ≤ 10^5), kiçik latın hərflərindən ibarətdir.
Çıxış verilənləri
Birinci sətirdə iki ədəd n və k (1 ≤ k ≤ 2n) - vəziyyətlərin sayı və keçidlərin sayı. Sonra k sətir, hər birində iki ədəd a_i, b_i (1 ≤ a_i, b_i ≤ n) və hərf c_i ('a' ≤ c_i ≤ '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.