Марковський цикл
Обмежений алгоритм Маркова складається з послідовності речень
s_1s_2...s_N → d_1d_2..d_N,
де s_i і d_i - символи з алфавіту A, B, C. Підрядок s_1s_2...s_N називається лівою, а d_1d_2..d_N - правою частиною речення.
Алгоритм виконується над заданим текстовим рядком, що складається з прописних латинських букв A, B, C, наступним чином: перебираються всі речення, починаючи з першого. Якщо ліва частина речення входить у текстовий рядок, то саме ліве входження замінюється правою частиною цього речення, і пошук знову починається з першого речення. Якщо жодне з речень не може бути застосовано, алгоритм зупиняється.
При виконанні алгоритму можливі два результати: або зупинка, або нескінченний цикл з певним періодом. За заданим рядком і набором речень алгоритму Маркова визначити кількість "ациклічних" (виконаних до початку циклу) кроків і довжину самого циклу. Якщо алгоритм зупиняється, то довжина циклу вважається нульовою, а всі виконані кроки - ациклічними.
Вхідні дані
У першому рядку знаходиться заданий рядок, а у наступних рядках - речення, по одному у рядку. Рядки можуть містити довільну кількість незначущих пропусків.
Довжина заданого текстового рядка і лівих частин речень - від 1 до 12 букв, кількість речень - від 1 до 50.
Вихідні дані
Вивести два цілих числа, відокремлених пропуском, - кількість ациклічних кроків і довжину циклу.