Pseudo automaton
Задано рядок S. Побудувати детермінований скінченний автомат, який приймає усі суфікси рядка S (і можливо інші скінченні рядки). Автомат повинен складатись з мінімального числа станів. Кожен стан автомату оголошується фінальним. Початковий стан має номер 1.
На зображенні нижче показано автомат з тестового прикладу для рядка "abacaba".
Вхідні дані
У єдиному рядку слово S, яке складається з рядкових латинських літер.
Вихідні дані
У першому рядку два числа N і K — кількість станів та кількість переходів. Далі K рядків, у кожному з яких по два числа a_i, b_i та літера c_i, які позначають наявність переходу зі стану a_i у b_i по літері c_i. Переходи можна виводити у довільному порядку. Якщо розв'язків декілька, можете вивести довільний з них.
Обмеження
1 ≤ |S| ≤ 5000
1 ≤ a_i, b_i ≤ N
'a' ≤ c_i ≤ 'z'