Markov cycle
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 A, B, C. The sequence s_1s_2...s_N is referred to as the left part, and d_1d_2..d_N is the right part of the rule.
The algorithm operates on a given text string made up of the uppercase Latin letters A, B, C, in the following manner: it iterates through all the rules starting from the first one. If the left part of a rule is found 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 potential outcomes when executing the algorithm: it either stops, or it enters an infinite cycle with a specific period. Given the initial string and the set of rules of the Markov algorithm, determine the number of "acyclic" steps (those executed before the cycle begins) and the length of the cycle itself. If the algorithm stops, the cycle length is zero, and all executed steps are acyclic.
Input
The first line contains the initial string, followed by lines containing the rules, one per line. Lines may include an arbitrary number of insignificant spaces.
The length of the initial text string and the left parts of the rules range from 1 to 12 letters, and the number of rules ranges from 1 to 50.
Output
Output two integers separated by a space: the number of acyclic steps and the length of the cycle.