Суфіксний автомат#4164
Суфіксним автоматом для рядка називається детермінований скінченний автомат , який розпізнає мову Suff(w) — множину суфіксів слова . Наприклад, суфіксний автомат для слова abbab повинен приймати в точності такі слова: \{\textbf{abbab}, \textbf{bbab}, \textbf{bab}, \textbf{ab}, \textbf{b}, \varepsilon\}. Автомат не повинен мати недосяжних станів та станів, з яких не можна досягти допустимого стану. Ми не вимагаємо, щоб автомат був мінімальним.
На малюнку зображено суфіксний автомат для слова abbab.
За даним скелетом суфіксного автомата деякого слова потрібно відновити суфіксний автомат. Задані стани, переходи, початковий стан і допустимі стани, але мітки на ребрах відсутні.
Ваше завдання — розставити мітки на ребрах так, щоб автомат став суфіксним автоматом деякого слова , а також знайти це слово. Для простоти вважайте, що розмір абетки необмежений, і ви можете використовувати числа від до як символи (значення ви обираєте).
Перший рядок вхідного файлу містить три цілі числа: , та — кількість станів, кількість переходів і кількість допустимих станів відповідно (2 \le n \le 200, 1 \le m \le 1000, 1 \le t \le n). Другий рядок містить цілих чисел — номери допустимих станів (стани нумеруються з , початковий стан має номер ).
Наступні рядків описують переходи: кожен рядок містить два цілі числа s_i і t_i і описує перехід з s_i у t_i.
У першому рядку вихідного файлу виведіть два числа і — довжину слова і розмір абетки. Використовуйте числа \{1, \ldots, k\} як елементи алфавіту. не повинно перевищувати .
У другому рядку виведіть чисел — слово .
У третьому рядку виведіть чисел — мітки для переходів автомата у порядку, в якому переходи наведено у вхідних даних.
Гарантується, що розв'язок завжди існує.
Приклад 1
