Sözlərin sayılması
Fales yay tətilini keçirmək üçün uzaq bir adaya getdi. Adada kifayət qədər darıxdırıcı olduğu üçün özünə məşğuliyyət tapmağa çalışdı. Bir gün o, yollar boyunca yazılmış sözlər və ifadələr gördü. Bəzilərini başa düşməsə də, bu, onu oyun icad etməkdən saxlamadı.
Bu oyunda bir söz düşünülür və həmin sözün yolun müəyyən bir seqmenti boyunca mətndə neçə dəfə rast gəldiyi sayılır. Fales bu oyunu bir neçə dəfə oynadıqdan sonra sözləri saymaq üçün sadə bir üsul tapdı və özünü daha mürəkkəb bir oyunda sınamağa qərar verdi. O, ərazinin xəritəsini çəkdi və hazırkı mövqeyindən evə gedə biləcəyi bütün limanlara gedən bütün mümkün yolları qeyd etdi. O, gördü ki, bütün yollar eyni başlaya bilsə də, nəticədə hamısı ayrılır və bir daha kəsişmir - hamısı müxtəlif limanlara aparır. Daha mürəkkəb oyunun qaydaları seçilmiş sözün müxtəlif yollar boyunca neçə dəfə göründüyünü saymağı tələb edirdi. Sizin proqramınız məhz bunu etməlidir.
Giriş verilənləri
Birinci sətir N (2 ≤ N ≤ 15000) tam ədədini ehtiva edir - növbəti sətirlərin sayını. Faylın növbəti (N-1) sətirinin hər biri düyünlər haqqında məlumat ehtiva edir. Bütün düyünlər ağac strukturunu təşkil edir. Xüsusilə, 0 düyünü başlanğıc nöqtəsini müəyyən edir və 1 ilə N-1 arasında nömrələnmiş bütün digər düyünlər ya çatallar, ya da limanlardır. Beləliklə, növbəti N-1 sətirin hər biri iki tam ədəd ehtiva edir ki, bunlar iki düyünü I, J (0 ≤ I, J ≤ N-1) və L simvol uzunluğunda S mətnini təqdim edir ( 1 ≤ L ≤ 1000), bu, I düyünündən J düyününə gedən yol seqmenti boyunca mətni müəyyən edir (burada I həmişə J düyününün sələfidir). Aydındır ki, 0 düyünə gedən yol yoxdur və heç bir yol limandan çıxmır. Faylın son sətiri Falesin düşündüyü sözü ehtiva edir.
Çıxış verilənləri
Çıxış faylı tək tam ədəd ehtiva etməlidir - bütün mümkün yollar boyunca sözün neçə dəfə fərqli göründüyü. Görünüş başlanğıc və son nöqtələrlə müəyyən edilir (son nöqtə başlanğıc nöqtədən sonra yolda rast gəlinir). Görünüş mövcuddur, əgər başlanğıc nöqtədən son nöqtəyə qədər (daxil olmaqla) bütün ardıcıl simvolların konkatenasiyası axtarılan sözü təşkil edirsə. Sözün görünüşü başqa bir görünüşdən fərqli hesab olunur, əgər onun fərqli son və/yaxud başlanğıc nöqtəsi varsa. Bütün simvollar kiçik latın əlifbası simvollarıdır.
