Автомат
Задано рядок 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. Переходи можна виводити у довільному порядку. Якщо розв'язків декілька, можете вивести довільний з них.