Şeir yazarı
Şair Vasya, şeir yazma prosesini asanlaşdırmaq üçün bir sonlu avtomat hazırlayıb. Bu avtomat N vəziyyətə malikdir və vəziyyətlər arasında K qafiyə ilə keçidlər mümkündür. Avtomat bir başlanğıc vəziyyətinə a və bir son vəziyyətinə b sahibdir. Vasya, avtomatın qəbul etdiyi qafiyə ardıcıllıqlarına uyğun olaraq şeirlər yaradır.
Vasya, şeirlərin monoton olmaması üçün hər keçiddən sonra avtomatı dəyişdirir. Yəni, əgər i vəziyyətindən j vəziyyətinə k qafiyəsi ilə keçid baş verərsə, Vasya i vəziyyətindən k qafiyəsi ilə çıxan bütün keçidləri və j vəziyyətinə k qafiyəsi ilə gələn bütün keçidləri silir.
Vasyanın avtomatını bu şəkildə istifadə edərək yarada biləcəyi maksimum şeir sayını tapmaq lazımdır. Hər hansı bir keçid silindikdən sonra, Vasya bu keçidi avtomatın ömrü boyu bərpa etməyəcək.
Giriş verilənləri
Giriş faylının birinci sətirində avtomatın vəziyyətlərinin sayı N (1 ≤ N ≤ 50), Vasya şeirlərində istifadə etdiyi qafiyələrin sayı K (1 ≤ K ≤ 50), başlanğıc və son vəziyyətlərin nömrələri a və b (1 ≤ a ≠ b ≤ N) olmaqla dörd tam ədəd verilir. İkinci sətir avtomatdakı keçidlərin sayını göstərən bir tam ədəd M (1 ≤ M ≤ 1000) ehtiva edir. Sonra M sətir gəlir, hər biri u_i, v_i, k_i formatında bir keçidi təsvir edir və bu, u_i vəziyyətindən v_i vəziyyətinə k_i qafiyəsi ilə keçidin mümkün olduğunu göstərir.
Çıxış verilənləri
Çıxış faylının birinci sətirində Vasya avtomatından istifadə edərək yarada biləcəyi maksimum şeir sayını Z göstərin. Sonra hər şeir üçün bir sətir olmaqla Z sətir göstərin. Şeirin təsvirini aşağıdakı formatda göstərin:
s_{1} k_1 s_2 k_2 … s_{l-1} k_{l-1} s_l
burada s_1 = a, s_l = b, k_i keçidlərin baş verdiyi qafiyələrdir və s_i keçid sırasındakı vəziyyətdir.