eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Pseudo automaton

Pseudo automaton

Лимит времени 1 секунда
Лимит использования памяти 256 MiB

Дана строка S. Построить детерминированный конечный автомат, принимающий все суффиксы строки S (и возможно другие конечные строки). Автомат должен состоять из минимального числа состояний. Каждое состояние автомата объявляется финальным. Начальное состояние имеет номер 1.

На изображении ниже показан автомат из тестового примера для строки "abacaba".

Входные данные

В единственной строке слово S, состоящее из строчных латинских букв.

Выходные данные

В первой строке два числа N и K — количество состояний и количество переходов. Далее K строк, в каждой из которых по два числа a_i, b_i и буква c_i, означающие наличие перехода из состояния a_i в b_i по букве c_i. Переходы можно выводить в любом порядке. Если решений несколько, можете вывести любое из них.

Ограничения

1|S|5000

1a_i, b_iN

'a' ≤ c_i ≤ 'z'

Пример

Входные данные #1
abacaba
Выходные данные #1
8 10
1 2 a
1 3 b
1 5 c
2 3 b
2 5 c
3 4 a
4 5 c
5 6 a
6 7 b
7 8 a