eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

У теорії формальних граматик і автоматів (ТФГіА) важливу роль відіграють так звані контекстно-вільні граматики (КС-граматики). КС-граматикою будемо називати четвірку, яка складається з множини N нетермінальних символів, множини T термінальних символів, множини P правил (продукцій) і початкового символу SN.

Кожна продукція pP має форму A→α, де A нетермінальний символ (AN), а α - рядок, який складається з термінальних та нетермінальних символів. Процес введення слова починається з рядка, який містить лише початковий символ S. Після цього на кожному кроці один з нетермінальних символів, які входять у поточний рядок, замінюється на праву частину однієї з продукцій, у якій він є лівою частиною. Якщо після такої операції отримується рядок, який містить лише термінальні, что процес виведення завершується.

У багатьох теоретичних задачах зручно розглядати так звані нормальні форми граматик. Процес зведення граматики до нормальної форме часто починається з усунення лівої рекурсії. У цій задачі ми будемо розглядати лише її частинний випадок, який називається безпосередньою лівою рекурсією. Кажуть, що правило A→α містить безпосередню ліву рекурсію, якщо першим символом рядка α є A.

Задано КС-граматику. Знайти кількість правил, які містять безпосередню ліву рекурсію.

Вхідні дані

Перший рядок вхідного файлу містить кількість n (1n1000) правил у граматиці. Кожен з наступних n рядків містить по одному правилу. Нетермінальні символи позначаються великими літерами латинського алфавіту, термінальні - рядковими. Ліва частина продукції відокремлюється від правої символами ->. Права частина продукції завжди непорожня і має довжину не більше 30 символів.

Вихідні дані

У вихідний файл виведіть відповідь до задачі.

Приклад

Вхідні дані #1
3
S->Sabc
S->A
A->AA
Вихідні дані #1
2