Sözlərin sayılması#4672
Thales yay tətili üçün uzaq bir adaya səyahət etdikdə, adanın kifayət qədər sakit olması səbəbindən özü üçün əyləncə axtarmağa başladı. Bir gün yol boyunca yazılmış söz və ifadələr gördü. Onların bir qismini başa düşməsə də, bir oyun qurmağa qərar verdi.
Bu oyunda bir söz seçilir və yolun müəyyən bir hissəsində həmin sözün neçə dəfə göründüyü sayılır. Bir neçə dəfə bu oyunu oynadıqdan sonra Thales sözləri saymağın sadə bir yolunu tapdı və daha mürəkkəb bir versiyada özünü sınamaq istədi. O, bölgənin xəritəsini çəkdi və mövcud olduğu nöqtədən evə qayıda biləcəyi müxtəlif limanlara gedən bütün mümkün yolları işarələdi. O müşahidə etdi ki, bütün yollar başlanğıcda eyni ola bilər, lakin sonradan ayrılır və heç vaxt yenidən birləşmir, hər biri ayrı bir limana aparır. Bu inkişaf etmiş oyunun qaydaları seçilmiş bir sözün müxtəlif yollar boyunca neçə fərqli dəfə baş verdiyini saymağı nəzərdə tutur. Sizin vəzifəniz isə bu proqramı yazmaqdır.
Birinci sətirdə (2 \leq N \leq 15000) — növbəti sətirlərin sayı verilir. Sonrakı N-1 sətirdə ağac quruluşu yaradan nöqtələr təsvir olunur. -cı nöqtə başlanğıc nöqtəsidir və digər bütün nöqtələr (-dən N-1-ə kimi nömrələnirlər) ya çatallaşma nöqtəsi, ya da limandır. Hər bir növbəti N-1 sətirdə iki tam ədəd , (0 \leq I, J \leq N-1) və uzunluğu simvollu sətri (1 \leq L \leq 1000) verilir, hansı ki, nöqtəsindən nöqtəsinə yol hissəsi və bu hissə boyunca yazılmış mətn təyin edir (burada həmişə -nin sələfidir). nöqtəsinə heç bir yol gəlmir və limandan heç bir yol çıxmır. Sonuncu sətirdə isə Thales-in düşündüyü söz verilir.
Çıxışa tək bir tam ədəd yazılmalıdır — bütün mümkün yollar boyunca sözün neçə fərqli baş verməsi mümkündür. Bir baş vermə, başlanğıc və bitiş nöqtələrinə görə təyin edilir (bitiş nöqtəsi başlanğıcdan sonra gəlir). Başlamaqdan bitiş nöqtəsinə qədər (hər ikisi daxil olmaqla) ardıcıl yerləşən bütün simvolların birləşməsi verilən sözü formalaşdırırsa, həmin baş vermə sayılır. Əgər bir baş vermə digərindən başlanğıc və ya bitiş nöqtəsinə görə fərqlənirsə, o, fərqli hesab olunur. Bütün simvollar kiçik latın hərflərindədir.
Nümunə 1