e-olymp
Задачі

Марковський цикл

Марковський цикл

Обмежений алгоритм Маркова складається з послідовності речень

s1s2...sNd1d2..dN,

де si і di - символи з алфавіту A, B, C. Підрядок s1s2...sN називається лівою, а d1d2..dN - правою частиною речення.

Алгоритм виконується над заданим текстовим рядком, що складається з прописних латинських букв A, B, C, наступним чином: перебираються всі речення, починаючи з першого. Якщо ліва частина речення входить у текстовий рядок, то саме ліве входження замінюється правою частиною цього речення, і пошук знову починається з першого речення. Якщо жодне з речень не може бути застосовано, алгоритм зупиняється.

При виконанні алгоритму можливі два результати: або зупинка, або нескінченний цикл з певним періодом. За заданим рядком і набором речень алгоритму Маркова визначити кількість "ациклічних" (виконаних до початку циклу) кроків і довжину самого циклу. Якщо алгоритм зупиняється, то довжина циклу вважається нульовою, а всі виконані кроки - ациклічними.

Вхідні дані

У першому рядку знаходиться заданий рядок, а у наступних рядках - речення, по одному у рядку. Рядки можуть містити довільну кількість незначущих пропусків.

Довжина заданого текстового рядка і лівих частин речень - від 1 до 12 букв, кількість речень - від 1 до 50.

Вихідні дані

Вивести два цілих числа, відокремлених пропуском, - кількість ациклічних кроків і довжину циклу.

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані
ABABC
C  ->A
AB ->BA
BAA->ABC
Вихідні дані
3 3