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

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

1 секунда

64 мегабайти

Легка

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

$s_{1} s_{2} ... s_{N}$ s_1s_2...s_N → $d_{1} d_{2} ... d_{N}$ d_1d_2...d_N,

де $s_{i}$ s_i та $d_{i}$ d_i — символи з алфавіту $A$ , $B$ , $C$ . Послідовність $s_{1} s_{2} ... s_{N}$ s_1s_2...s_N називається лівою частиною, а $d_{1} d_{2} ... d_{N}$ d_1d_2...d_N — правою частиною правила.

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

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

Вхідні дані

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

Довжина початкового рядка та лівих частин правил — від $1$ до $12$ літер, кількість правил — від $1$ до $50$ .

Вихідні дані

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

Приклади

Приклад 1