eolymp
bolt
Try our new interface for solving problems
Problems

Левая рекурсия

Левая рекурсия

\includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg} В теории формальных грамматик и автоматов (ТФГиА) важную роль играют так называемые \textit{контекстно-свободные грамматики} (КС-грамматики). КС-грамматикой будем называть четвёрку, состоящую из множества \textbf{N} нетерминальных символов, множества \textbf{T} терминальных символов, множества \textbf{P} правил (продукций) и начального символа \textbf{S} \textbf{N}. \includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg} \includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg} Каждая продукция \textbf{p} \textbf{P} имеет форму \textbf{A}→α, где \textbf{A} нетерминальный символ (\textbf{A} \textbf{N}), а α - строка, состоящая из терминальных и нетерминальных символов. Процесс вывода слова начинается со строки, содержащей только начальный символ \textbf{S}. После этого на каждом шаге один из нетерминальных символов, входящих в текущую строку, заменяется на правую часть одной из продукций, в которой он является левой частью. Если после такой операции получается строка, содержащая только терминальные, что процесс вывода заканчивается. Во многих теоретических задачах удобно рассматривать так называемые \textit{нормальные формы} грамматик. Процесс приведения грамматики к нормальной форме часто начинается с устранения \textit{левой рекурсии}. В этой задаче мы будем рассматривать только её частный случай, называемый \textit{непосредственной левой рекурсией}. Говорят, что правило \textbf{A}→α содержит непосредственную левую рекурсию, если первым символом строки α является \textbf{A}. Задана КС-грамматика. Найти количество правил, содержащих непосредственную левую рекурсию. \InputFile Первая строка входного файла содержит количество \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{1000}) правил в грамматике. Каждая из последующих \textbf{n} строк содержит по одному правилу. Нетерминальные символы обозначаются заглавными буквами латинского алфавита, терминальные - строчными. Левая часть продукции отделяется от правой символами \textbf{->}. Правая часть продукции всегда непуста и имеет длину не более \textbf{30} символов. \OutputFile В выходной файл выведите ответ на задачу.
Time limit 1 second
Memory limit 64 MiB
Input example #1
3
S->Sabc
S->A
A->AA
Output example #1
2