Problems
Марковский цикл
Марковский цикл
Ограниченный алгоритм Маркова состоит из последовательности предложений
\textbf{s_1s_2...s_N} → \textbf{d_1d_2..d_N},
где \textbf{s_i} и \textbf{d_i} - символы из алфавита \textbf{A}, \textbf{B}, \textbf{C}. Подстрока \textbf{s_1s_2...s_N} называется левой, а \textbf{d_1d_2..d_N} - правой частью предложения.
Алгоритм выполняется над исходной текстовой строкой, состоящей из прописных латинских букв \textbf{A}, \textbf{B}, \textbf{C}, следующим образом: перебираются все предложения начиная с первого. Если левая часть предложения входит в текстовую строку, то самое левое вхождение заменяется правой частью этого предложения, и поиск вновь начинается с первого предложения. Если ни одно предложение не может быть применено, алгоритм останавливается.
При выполнении алгоритма возможны два результата: либо остановка, либо бесконечный цикл с определенным периодом. По данной строке и набору предложений алгоритма Маркова определить количество "ациклических" (выполненых до начала цикла) шагов и длину самого цикла. Если алгоритм останавливается, то длина цикла считается нулевой, а все выполненные шаги - ациклическими.
\InputFile
В первой строке находится исходная строка, а в следующих строках - предложения, по одному в строке. Строки могут содержать произвольное количество незначащих пробелов.
Длина исходной текстовой строки и левых частей предложений - от \textbf{1} до \textbf{12} букв, количество предложений - от \textbf{1} до \textbf{50}.
\OutputFile
Вывести два целых числа, разделенных пробелом, - количество ациклических шагов и длину цикла.
Input example #1
ABABC C ->A AB ->BA BAA ->ABC
Output example #1
3 3