Automaton#4593
Create a deterministic finite-state automaton that accepts all suffixes of a given string (and possibly other finite strings as well). The automaton must consist of a minimal number of states and no more than transitions. Every state of the automaton is considered a final state. The initial state is numbered .
The image below shows the automaton built for the test example string .
The only input line contains the string , consisting of lowercase Latin letters.
On the first line, print two integers and (1 \leq k \leq 2n) — the number of states and the number of transitions, respectively.
Then print lines, each containing two integers a_i, b_i (1 \leq a_i, b_i \leq n) and a lowercase letter c_i ('a' \leq c_i \leq 'z'), meaning that there is a transition from state a_i to state b_i by the letter c_i.
You may output the transitions in any order. If there are multiple valid solutions, output any of them.
Example 1