e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

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

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

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

s1s2...sNd1d2..dN,

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

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

При выполнении алгоритма возможны два результата: либо остановка, либо бесконечный цикл с определенным периодом. По данной строке и набору предложений алгоритма Маркова определить количество "ациклических" (выполненых до начала цикла) шагов и длину самого цикла. Если алгоритм останавливается, то длина цикла считается нулевой, а все выполненные шаги - ациклическими.

Входные данные

В первой строке находится исходная строка, а в следующих строках - предложения, по одному в строке. Строки могут содержать произвольное количество незначащих пробелов.

Длина исходной текстовой строки и левых частей предложений - от 1 до 12 букв, количество предложений - от 1 до 50.

Выходные данные

Вывести два целых числа, разделенных пробелом, - количество ациклических шагов и длину цикла.

Time limit 1 second
Memory limit 64 MiB
Input example #1
ABABC
C    ->A
AB ->BA
BAA ->ABC
Output example #1
3 3