Подсчет слов
Когда Фалес выехал на отдаленный остров, для того чтобы провести летний отпуск, ему пришлось искать, чем бы заняться, т.к. на острове было достаточно скучно. Однажды, Фалес заметил, что вдоль дорог написаны слова или фразы. Он не мог понять некоторые из них, но это не остановило его от изобретения игры.
Для того чтобы сыграть в эту игру, нужно выдумать слово и посчитать, как много раз оно встречается в тексте вдоль определенного сегмента дороги. После того, как Фалес сыграл в эту игру несколько раз, он изобрел простой способ подсчета слов, и решил испробовать себя в более сложной игре. Фалес нарисовал карту местности и отметил все возможные пути от его текущего положения до всех портов, откуда он мог бы уплыть домой. Он заметил, что хотя все пути могут начинаться одинаково, они все в итоге расходятся и больше никогда не пересекаются – все они приводят к разным портам. Правила более сложной игры требовали посчитать количество различных появлений выбранного слова вдоль различных путей. Ваша программа должна сделать именно это.
Входные данные
Первая строка содержит целое число N (2 ≤ N ≤ 15000) – число последующих строк. Каждая из следующих (N-1)-й строк файла содержит данные об узлах. Все узлы формируют древовидную структуру. В частности, узел 0 представляет исходную точку, а все остальные узлы, пронумерованные от 1 до N-1, представляют развилки или порты. Таким образом, каждая из последующих N-1 строк содержит два целых числа представляющих два узла I, J (0 ≤ I, J ≤ N-1) и текст S длинной L символов (1 ≤ L ≤ 1000), которые задают сегмент дороги от узла I к узлу J (где I всегда предшественник J) с текстом вдоль сегмента дороги. Очевидно, что нет дороги ведущей к узлу 0, и ни одна дорога не выходит из порта. Последняя строка файла содержит задуманное Фалесом слово.
Выходные данные
Выходной файл должен содержать единственное целое число – количество различных появлений слова вдоль всех возможных путей. Появление идентифицируется начальной и конечной точками (конечная точка встречается на пути позже начальной). Появление существует, когда конкатенация всех последовательных символов от начальной до конечной точки (включительно) формирует искомое слово. Появление слова считается отличным от другого появления, когда у него иная конечная и/или начальная точка. Все символы – малые символы латинского алфавита.
