Pseudo automaton#4608
Given string . Create deterministic finite-state automaton, that accepts all suffixes of (and probably other finite strings). Automaton must consist of minimal number of states. Each state of the automaton is final. Starting state has number .
Image below shows automaton from test sample for string "abacaba".
The only line contains string , consisting of lowercase latin letters.
In the first line, print two integers and --- the number of states and the number of transitions respectively. Next, lines follow, each having two numbers a_i, b_i and letter c_i, meaning transition from state a_i to b_i by letter c_i. You can output transitions in any order. If there are multiple solutions, output any of them.
Constraints
1 \le |S| \le 5000
1 \le a_i, b_i \le N
'a' \le c_i \le 'z'
Example 1