Ограниченный алгоритм Маркова состоит из последовательности предложений
s1s2...sN -> d1d2...dN,
где s
i и d
i - символы из алфавита A, B, C. Подстрока s
1s
2...s
N называется левой частью, а d
1d
2...d
N - правой частью предложения.
Алгоритм выполняется над исходной текстовой строкой, состоящей из прописных латинских букв A, B, C, следующим образом: перебираются все предложения, начиная с первого. Если левая часть предложения входит в текстовую строку, то самое левое вхождение заменяется правой частью этого предложения, и поиск вновь начинается с первого предложения. Если ни одно предложение не может быть применено, алгоритм останавливается.
При выполнении алгоритма возможны два результата: либо остановка, либо бесконечный цикл с определенным периодом. По данной строке и набору предложений алгоритма Маркова определить количество "ациклических" (выполненных до начала цикла) шагов и длину самого цикла. Если алгоритм останавливается, то длина цикла считается нулевой, а все выполненные шаги - ациклическими.
Входные данные
В первой строке находится исходная текстовая строка, а в следующих строках - предложения, по одному в строке. Строки могут содержать произвольное количество незначащих пробелов.
Ограничения: длина исходной текстовой строки и левых частей предложений - от 1 до 12 букв, количество предложений - от 1 до 50.
Выходные данные
Вывести два целых числа, разделённых пробелом - количество ациклических шагов и длину цикла.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
AB
B->C
A->A
|
1 1
|
|
2
|
A
B-> C
|
0 0
|