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