Markov cycle#1089
A restricted Markov algorithm consists of a sequence of rules:
s_1s_2...s_N → d_1d_2...d_N,
where s_i and d_i are symbols from the alphabet , , . The sequence s_1s_2...s_N is called the left part, and d_1d_2...d_N is the right part of the rule.
The algorithm operates on a given text string consisting of uppercase Latin letters , , as follows: all rules are checked starting from the first. If the left part of a rule occurs in the text string, the leftmost occurrence is replaced with the right part of that rule, and the process restarts from the first rule. If none of the rules can be applied, the algorithm terminates.
There are two possible outcomes for the algorithm: it either stops, or it enters an infinite cycle with a certain period. Given the initial string and the set of rules for the Markov algorithm, determine the number of "acyclic" steps (those performed before the start of the cycle) and the length of the cycle itself. If the algorithm terminates, the cycle length is considered zero and all steps performed are acyclic.
The first line contains the initial string, and the following lines contain the rules, one per line. Lines may contain an arbitrary number of insignificant spaces.
The length of the initial text string and the left parts of the rules is from to letters, the number of rules is from to .
Output two integers separated by a space: the number of acyclic steps and the length of the cycle.
Example 1