Автомат
Дана строка s. Построить детерминированный конечный автомат, принимающий все суффиксы строки s (и возможно другие конечные строки). Автомат должен состоять из минимального числа состояний - n и не более чем 2n переходов. Каждое состояние автомата объявляется финальным. Начальное состояние имеет номер 1.
На изображении ниже показан автомат из тестового примера для строки "abacaba".
Входные данные
В единственной строке слово s (1 ≤ |s| ≤ 10^5), состоящее из строчных латинских букв.
Выходные данные
В первой строке два числа n и k (1 ≤ k ≤ 2n) - количество состояний и количество переходов. Далее k строк, в каждой из которых по два числа a_i, b_i (1 ≤ a_i, b_i ≤ n) и буква c_i ('a' ≤ c_i ≤ 'z'), означающие наличие перехода из состояния a_i в b_i по букве c_i. Переходы можно выводить в любом порядке. Если решений несколько, можете вывести любое из них.